Have you been iterating through your workday. Writing wasteful O(n) for loops, and just wishing there was a better way? Well I have good news for you! There are many ways to loop through elements in a collection using Kotlin. Traversing a collection is a very common task and sometimes we need to traverse very large collection, or maybe we just need to traverse a subset of numbers within collection.
We can create collections from collections by logically defining subsets, subarrays & subsequences.
- Subarray – is a continuous set of elements within an array.
- Subsequence – a set of elements that maintains some form of order, but are not continuous.
- Subset – smaller set of elements in a collection but is not in continuous or sequential order.
When a collection is very large we should use an algorithm to traverse it. Algorithms become increasingly effective when you need to work on very large datasets quickly. To work quickly, an algorithm might only iterate through a smaller subarray of the collection or use traversal patterns.
To understand traversal patterns, its good to know what the Iterable<T> is under the hood. The Collection interface extends the Iterable interface.
public inline fun <T> Iterable(crossinline iterator: () -> Iterator<T>): Iterable<T> = object : Iterable<T> {
override fun iterator(): Iterator<T> = iterator()
}
As you can see, the interface simply exposes the iterator class which is only capable of getting the next element if one is available.
public interface Iterator<out T> {
/**
* Returns the next element in the iteration.
*/
public operator fun next(): T
/**
* Returns `true` if the iteration has more elements.
*/
public operator fun hasNext(): Boolean
}
When you place a collection in a for loop. The iterator will call the next() and hasNext() functions to traverse the collection. The next function will return the first element in the array or subarray the first time it’s called and return the next element on sequential calls to next.
For each iteration the hasNext function is first called to see if an iteration can happen and then the next function gets called. Rather than have our ‘for’ operation call the next & hasNext functions, we could do this manually.
val arr = intArrayOf(1,2,3,4,5) //get a copy of the iterator function used by the IntArray val iterator = arr.iterator() //loop through elements in the array manually println(iterator.next()) println(iterator.next()) println(iterator.next()) println(iterator.next()) println(iterator.next()) println(iterator.next())
As you can see there are 5 elements in the array and we’re calling next 6 times. This will result in an output of 1,2,3,4,5 then an index our of bounds exception will be thrown. This is because we never called hasNext before calling next.
forEach
While the iterator is useful for manually traversing a collection there are many iterables we can use or automatic traversal. If we plan on looping through every element in a collection, we can call the for each method.
val arr = intArrayOf(1,2,3,4,5)
arr.forEach { println(it) }
//returns 12345
arr.forEach { num ->
println(num)
}
//returns 12345
This method is best when you must loop through every single element in a collection. You can access the next element during the iteration by reference ‘it’. To be more representative of the element you can give it a name by adding name -> before the operation.
arr.forEachIndexed { index, elem ->
if(arr[index] == elem){
println("same element")
}
}
forEachIndexed
This operation is more flexible than forEach because we can change the value of the element while iterating. If you tried to set the element in a forEach loop, then you would see that it is a val and cannot be reassigned. This is not the case when we use the index to access an element in an array as you can see by this example.
val arr = intArrayOf(1,2,3,4,5)
arr.forEachIndexed { index, elem ->
if(arr[index] == elem){
println("same element")
arr[index] = 99
}
}
for
The for operation is a much more flexible function, because are not forced to loop through every single element. But for the sake of completeness, here’s a regular O(n) for loop.
for(car in cars){
//Do something with car
}
IntRanges
We can also loop through statically defined IntRange’s.
for(i in 1..10)
Because the indices of an array is also an IntRange type we can get this range directly by calling the indices property of the array.
for(i in cars.indices)
step increments
When looping through a range of Int’s the index will increment or decrement 1 value in the array for each call to next(). When we iterate through ranges, we can control how much we increment by using the ‘step’ function. Given a scenario where you only needed to operate through ever even number, you could do so by stepping 2.
for(i in cars.indices step 2)
Iterating backwards
There are a few was to do this so choose the method that fits your logic best. If your goal is to loop through a range of consecutive numbers backwards, then using downTo is a great way to do this.
for(i in 10 downTo 1)
What do we do for scenarios when we’re not looping through sequential numbers? Well, we can loop through our indices in reversed order. This also gives us the ability to mutate the element in the array we’re iterating through.
for(i in a.indices.reversed()){
a[i] = 99
}
Looping through factors
The factor of a number is a number smaller than a given number than can divide the given number completely without leaving a remainder. The modulo % operator can be used to tell us if a number divides by another number will leave a remainder. Working with just the indices it’s trivial to see how we can loop through all the elements who’s index is a factor of the size of the array.
val factors = (1..A.size/2).filter { A.size % it == 0 } + A.size
for(f in factors){
A[f] = 123
}
Cancelling an iteration
At any time we can skip to the next function by calling ‘continue’ or ‘break’. The continue function will skip to the next element if there is one, otherwise it will terminate the loop. The break function will terminate the loop all together.
for(i in a){
if(i == -38){
break
} else
continue
println("This code is never executed")
}
Filter
We can filter out elements that we font want to iterate by calling the filter method. This method will only return elements that meet the criteria defined by our conditions. The filter method has a time complexity of O(log n) and will improve the efficiency of your functions by reducing the number of iterations required for looping.
for(i in a.filter { it.type == "truck" })
While
As you’ve seen in many programming languages, the while loop while execute code while some condition is true. The code within the while block will executed for eternity, or until your device dies or the application runs out of memory. This is why it’s important to have logic that will eventually break the while loop.
var j = 0
while(1==1){
println(j++)
}
A While loop can have a companion Do operation chained to it. The Do operation will only be triggered once, and the while condition continues to execute until the condition is false.
do {
print("Whats your name?")
input = readLine()!!
sum += input
} while (input == "Jon")
Summary
We learned about some of the canned approaches to looping through iterations in Kotlin which can be a foundation upon much is built. We can modify increments, filter data, loop through sub sequential arrays using these operations. I would encourage you to think outside the box and come up with strategies that require less iterations to optimize your logic.