I bought "Introduction to Design Patterns Learned in Java Language [^ 1]" by Hiroshi Yuki, who is famous for "Math Girls" [^ 2]. Since this is a great opportunity, I will make study notes while implementing it with Swift, which I usually use. This article was created with reference to "Chapter 1 Iterator Counting One by One".
When I first touched the Iterator pattern (it was a JavaScript Iterator), I had no idea what I was happy about.
This time, I feel that I somehow realized the joy of the Iterator pattern while moving my hands to implement it concretely and looking at the source code of Swift's Sequence and map.
I hope it will be helpful for those who have similar feelings!
A design pattern used when scanning an entire collection of things in sequence, such as Array or Dictionary. It's a bit long quote, but in "Introduction to Design Patterns Learned in Java [^ 1]", it is explained as follows.
If i is incremented by 1 in the for statement i ++, it means that the entire elements of the array arr are scanned in order from the beginning. In the design pattern, the function of the variable i used here is abstracted and generalized. Iterator pattern We call it>. The Iterator pattern is for processing when a lot of things are gathered, pointing to them in order and scanning the whole. The English word iterate means to "repeat" something. [^ 3]
The interface of the type that scans the element. It seems that there are various schools, but the following protocols can be considered as simple ones.
protocol MyIteratorProtocol {
//Type of element held by array etc.
associatedtype Element
//A method that returns if the next element is present
func hasNext() -> Bool
//A method that returns the next element during a scan
mutating func next() -> Element?
}
It is an interface of a type that holds a collection of "something" such as an array or Dictionary, and has a method to generate an iterator.
protocol AggregateProtocol {
//Type of element held by array etc.
associatedtype Element
//The Iterator type returned by the iterator method, Element must match
associatedtype Iterator: MyIteratorProtocol where Iterator.Element == Element
//Method to generate iterator
func iterator() -> Iterator
}
ConcreteIterator / ConcreteAggregate
These are concrete types that implement (compliant) the Iterator interface and Aggregate interface.
Here, as an example, we will implement the BirdCage type that holds a set of Bird types and its Iterator, the BirdCageIterator.
Bird
A struct that just holds the name.
Bird.swift
struct Bird {
let name: String
}
BirdCage
Defines a struct that holds a set of Birds. Implement the iterator method by setting the associatedType alias to comply with the Aggregate Protocol. For simplicity, we'll keep the Bird set itself as an array.
BirdCage.swift
struct BirdCage: AggregateProtocol {
//Set a specific type for associatedType
typealias Element = Bird
typealias Iterator = BirdCageIterator
//Implement a method that returns an iterator
func iterator() -> Iterator {
BirdCageIterator(birds: birds)
}
//Here we keep the set as an Array for simplicity
private var birds: [Bird] = []
//Method to put bird in a bird cage
mutating func put(bird: Bird) {
birds.append(bird)
}
//Specify the index and look at the bird
func peek(birdOf index: Int) -> Bird? {
index < birds.count ? birds[index] : nil
}
}
BirdCateIterator
Defines an Iterator for BirdCate. Implement the hasNext / next method by setting the associatedType alias to comply with the MyIteratorProtocol.
BirdCateIterator.swift
struct BirdCageIterator: MyIteratorProtocol {
//Set a specific type for associatedType
typealias Element = Bird
//Hold an array of sets to scan
private let birds: [Bird]
private var index: Int = 0
init(birds: [Bird]) {
self.birds = birds
}
func hasNext() -> Bool {
index < birds.count
}
//When the method is called, advance its own index by one
mutating func next() -> Bird? {
let bird = index < birds.count ? birds[index] : nil
index += 1
return bird
}
}
Define and call a function that prints each element of the set.
The point is to define the function with type parameters like ʻAggregate: AggregateProtocol. Functions implemented in this way can be used for all types implemented in the Iterator pattern (types that comply with ʻAggregateProtocol).
func printElements<Aggregate: AggregateProtocol>(of aggregate: Aggregate) {
var iterator = aggregate.iterator()
while iterator.hasNext() {
let element = iterator.next()
print(String(describing: element!))
}
}
var cage = BirdCage()
cage.put(bird: Bird(name: "Budgerigar"))
cage.put(bird: Bird(name: "Cockatiel"))
cage.put(bird: Bird(name: "Parakeet"))
cage.put(bird: Bird(name: "Parrot"))
printElements(of: cage)
// Bird(name: "Budgerigar")
// Bird(name: "Cockatiel")
// Bird(name: "Parakeet")
// Bird(name: "Parrot")
The printElements function mentioned earlier is implemented not for the concrete BirdCage type, but for the "ʻAggregate general" that conforms to the "" Aggregate Protocol ".
So, regardless of how the specific BirdCage or BirdCageIterator implements the ʻiteratorornext methods, printElements can use the argument ʻaggregate: Aggregate. I can do it.
To enjoy this advantage and use printElements more conveniently, define printElements in the extension of ʻAggregateProtocol`.
AggregateProtocol.swift
extension AggregateProtocol {
func printEelements() {
var iterator = self.iterator()
while iterator.hasNext() {
let element = iterator.next()
print(String(describing: element!))
}
}
}
var cage = BirdCage()
cage.put(bird: Bird(name: "Budgerigar"))
cage.put(bird: Bird(name: "Cockatiel"))
//You can call printElements from any struct that complies with AggregateProtocol!
cage.printElements()
Actually, Swift has ʻIterator Protocol` as standard [^ 4].
public protocol IteratorProtocol {
associatedtype Element
mutating func next() -> Element?
}
And the Sequence protocol, which various structs such as Array, Dictionary, and String conform to, uses ʻIterator Protocol` internally [^ 5].
public protocol Sequence {
associatedtype Element
associatedtype Iterator: IteratorProtocol where Iterator.Element == Element
__consuming func makeIterator() -> Iterator
...
}
The definition of this part is the ʻAggregate Protocolitself created in this article. Exactly this protocol calledSequence` is implemented using the Iterator pattern.
For example, the map method, familiar with Array, is actually implemented in the extension of the Sequence protocol.
Therefore, you can call the map method not only for Array and Range, but also for Dictionary and String.
[1, 2, 3].map { $0 + 1 }
(0...2).map { $0 * 2 }
["key1": 1, "key2": 2].map { (k, i) in i }
"Hello, world!".map { $0.uppercased() }
And iterator is used inside the map method [^ 6].
The internal implementation of Array, Dictionary, Range, String and the implementation of Iterator defined in each should be different, but the map method can be implemented by one implementation through the interface of ʻIterator Protocol`.
extension Sequence {
...
@inlinable
public func map<T>(
_ transform: (Element) throws -> T
) rethrows -> [T] {
let initialCapacity = underestimatedCount
var result = ContiguousArray<T>()
result.reserveCapacity(initialCapacity)
var iterator = self.makeIterator()
// Add elements up to the initial capacity without checking for regrowth.
for _ in 0..<initialCapacity {
result.append(try transform(iterator.next()!))
}
// Add remaining elements, if any.
while let element = iterator.next() {
result.append(try transform(element))
}
return Array(result)
}
}
Did you feel the joy of the Iterator pattern? Stay tuned for the next pattern!
-Introduction to Design Patterns Learned in Java Language
[^ 1]: Introduction to Design Patterns Learned in Java Language [^ 2]: As of September 1, 2020, the Kindle version is half price during the summer sale! [^ 3]: Supplementary Revised Edition Introduction to Design Patterns Learned in Java Language Chapter 1 Iterator Enumeration One by One
Recommended Posts