Iterator Design Pattern
When we were discussing the Composite design pattern in the previous chapter, we noted that the design pattern felt a bit incomplete. Now is the time to reunite the twins separated at birth. Much like Arnold Schwarzenegger and Danny DeVito, they're very different, but complement each other well.
One, two... many We're back to our squads and platoons in our CatsCraft 2: Revenge of the Dogs strategy game. As you may remember from the previous blog, Squad consists of InfantryUnits:
interface InfantryUnit
class Squad(val infantryUnits: MutableList<InfantryUnit> = mutableListOf()) {
}
Each squad should also get a commander now. The commander of a squad called Sergeant is also an InfantryUnit:
class Squad(...) {
val commander = Sergeant()
}
class Sergeant: InfantryUnit Please disregard the fact that our sergeant doesn't have a name and gets created on the fly. We're two days short of releasing this game and beating the competition. Names are not important now. The platoon is a collection of squads, and it also has a commander, called Lieutenant:
class Platoon(val squads: MutableList<Squad> = mutableListOf()) {
val commander = Lieutenant()
}
class Lieutenant: InfantryUnit What our CEO wants is a platoon, and to be able to know which units it consists of. So, when we have the following lines in our code:
val rangers = Squad("Josh", "Ew an", "Tom")
val deltaForce = Squad("Sam", "Eric", "William")
val blackHawk = Platoon(rangers, deltaForce)
for (u in blackHawk) {
println(u)
}
We would print by order of seniority: Lieutenant, Sergeant, Josh, Ewan, Tom, ... Nowadays, this task may seem trivial to you, especially if you come from the Java world. But back in '94, data structures were mostly arrays of primitive types. Yes, Array<Int>, I'm looking at you. Iterating over an array wouldn't be that hard, even in Java:
int[] array = new int[] {1, 2, 3};
for (int i = 0; i < array.length; i++) {
System.out.println(i);
}
What are we to do with something much more complex?
Running through the values If you're using an IDE such as IntelliJ, it will give you a hint on what the problem may be: for (u in blackHawk) { <== For-loop range must have an 'iterator()' method
// Wanted to do something here
}
So, our Platoon needs to have a function called iterator(). And since it's a special function, we'll need to use the operator keyword. operator fun iterator() = ... What our function returns is an anonymous object that implements the
Iterator<T> interface: ... = object: Iterator<InfantryUnit> {
override fun hasNext(): Boolean {
// Are there more objects to iterate over?
}
override fun next(): InfantryUnit {
// Return next InfantryUnit
}
}
The idea behind the iterator design pattern is to separate how the object stores data (in our case, it's something like a tree) and how we can go over this data. As you may know, trees can be iterated in one of two ways: depth-first (also known as depth-first search (DFS)) breadth-first (also known as breadth-first search (BFS)) But do we really care when we need to fetch all the elements? So, we separate these two concerns: storage aside, repeating aside. To go over all the elements, we need to implement two methods, one to fetch the next element, and one to let the loop know when to stop. As an example, we'll implement this object for Squad. For Platoon, the logic would be similar, but requires a bit more math. First, we need a state for our iterator. It will remember that the last element is returned:
operator fun iterator() = object: Iterator<InfantryUnit> {
var i = 0
// More code here
}
Next, we need to tell it when to stop. In our case, the total number of elements is all the units of the squad, plus the sergeant:
override fun hasNext(): Boolean {
return i < infantryUnits.size + 1
}
Finally, we need to know which unit to return. If that was the first call, we'll return the sergeant. The next calls will return one of the squad members:
override fun next() =
when (i) {
0 -> commander
else -> infantryUnits[i - 1]
}.also { i++ }
Note that we want to return the next unit, but also to increase our counter.For that, we use the also {} block. That's only one of the usages of this pattern.
The same object may also have more than one iterator. For example, we could have the second iterator for our squad that would go over elements in reverse order. To use it, we'll need to call it by name:
for (u in deltaForce.reverseIterator()) {
println(u)
}
Since it's just a simple function that returns an iterator now, we don't need the operator keyword: fun reverseIterator() = object: Iterator<InfantryUnit> {
// hasNext() is same as before
}
The only changes are coming in the next() method:
override fun next() =
when (i) {
infantryUnits.size -> commander
else -> infantryUnits[infantryUnits.size - i - 1]
}.also { i++ } Sometimes, it also makes sense to receive an iterator as a parameter for a function: fun <T> printAll(iter: Iterator<T>) {
while (iter.hasNext()) {
println(iter.next())
}
}
This function will iterate over anything that supplies an iterator:
printAll(deltaForce.iterator())
printAll(deltaForce.reverseIterator())
This will print our squad members twice, once in regular and once in reverse order. As a regular developer who doesn't invent new data structures for his or her living, you may now implement iterators often. But it's important to know how they work behind the scenes nevertheless.
Code Examples :
1. In Kotlin :
package designpatterns
fun main(args: Array<String>) {
val rangers = Squad("Abhi", "Abhinaw", "Tripathi")
val deltaForce = Squad("Nitu", "Shukla", "Tripathi")
val blackHawk = Platoon(rangers, deltaForce)
printAll(deltaForce.iterator())
printAll(deltaForce.reverseIterator())
}
fun <T> printAll(iter: Iterator<T>) {
while (iter.hasNext()) {
println(iter.next())
}
}
class Squad(private val infantryUnits: MutableList<InfantryUnit> =
mutableListOf()) {
val commander = Sergeant()
constructor(s0: String, s1: String, s2: String) : this() {
infantryUnits.add(object : InfantryUnit {})
infantryUnits.add(object : InfantryUnit {})
infantryUnits.add(object : InfantryUnit {})
}
operator fun iterator() = object : Iterator<InfantryUnit> {
var i = 0
override fun hasNext(): Boolean {
return i < infantryUnits.size + 1
}
override fun next() =
when (i) {
0 -> commander
else -> infantryUnits[i - 1]
}.also { i++ }
}
fun reverseIterator() = object : Iterator<InfantryUnit> {
var i = 0
override fun hasNext(): Boolean {
return i < infantryUnits.size + 1
}
override fun next() =
when (i) {
infantryUnits.size -> commander
else -> infantryUnits[infantryUnits.size - i - 1]
}.also { i++ }
}
}
class Platoon(val squads: MutableList<Squad> = mutableListOf()) {
val commander = Lieutenant()
constructor(squads: Squad, deltaForce: Squad) : this()
operator fun iterator() = object : Iterator<InfantryUnit> {
var i = 0
override fun hasNext(): Boolean {
return false
}
override fun next(): InfantryUnit {
return commander
}
}
}
interface InfantryUnit
class Sergeant : InfantryUnit
class Lieutenant : InfantryUnitOutput:
Sergeant@27bc2616
Squad$1@9807454
Squad$2@3d494fbf
Squad$3@1ddc4ec2
Squad$3@1ddc4ec2
Squad$2@3d494fbf
Squad$1@9807454
Sergeant@27bc2616
2. In Java :
package designpatterns;
public class IterateArrayExample {
public static void main(String[] args) {
int[] array = new int[] {1, 2, 3};
for (int i = 0; i < array.length; i++) {
System.out.println(i);
}
}
}
No comments:
Post a Comment