Parameterizing for loops
We’ve seen a few variants of for loops in our day-to-day programming stretches on Java. All of them have different syntaxes and ease of use that depends on why that was designed. In spite of that, they follow a standard structure under the hood. A standard for loop iteration has 3 parts; initialization, validity check and an incrementor.
This article is written by a Java developer and other languages already have this type of iterator available out of the box, but today, I came up with this class using some concepts of functional programming and I’d like to share that.
Standard: for (int i = 0; i < n; i++) {}
Initialization: int i = 0
Validation: i < n
Incrementor: i++
There has never been any harm in using the full syntax in performing computations. It works out fantastic and repeats the function body for each iteration index.
So, in an array, we can iterate from the start index to end index by incrementing 1 on each iteration. Imagine, you’ve done some calculation by iterating from left to right and now, you’ve to repeat the same computation in the reverse order. How would you go about it?
for (int i = 1; i ≤ n; i++) {}
for (int i = n; i ≥ 1; i — ) {}
We’ve to write different for loops for each direction of iteration. Can these two be done with a single loop. The computation would be done separately but I’d not like to write two different for loops.
If you look closely, incrementor is nothing but 1 or -1 as that is the change between the values of iterator. That can easily be parameterized using an integer. The same can be said for the initialization section.
But, the validation is a boolean check and that can only be parameterized by a Predicate function.
Predicate function is one among the family of functional interfaces available in Java, provided by the java.util.function library. Predicate is a function which takes a value as input and returns a true/false based on some condition.
I don’t just need the validation as a externalized parameter. There should be a full construct of a for loop. I started from a simple for loop like the one written above and after some time spending on refactoring it using functional interfaces, a For class unveiled itself, which looked something like this.
public static class For {
int start;
IntPredicate end;
IntUnaryOperator next; // left <= right; direction decided by sign of increment.
public static For of(int left, int right, int increment) {
For f = new For();
f.start = increment > 0 ? left : right;
f.end = increment > 0 ? x -> x <= right : x -> x >= left;
f.next = x -> x + increment;
return f;
}
}
This class exposes a single method which takes in left and right bounds and a incrementing integer and returns the For instance. The motivation was parameterizing for loop conditions and this class provides all the three and can be passed around in methods, allowing us to avoid writing separate code for 2 directions of for loop iteration.
Following is an example of these values will be used in a for loop.
For loop = For.of(1, n, 1)for (
int i = loop.start;
loop.end.test(i);
i = loop.next.applyAsInt(i)
) {}
The for loop may look a bit weird right now as it now has a lot of things. Good thing is that you don’t have to worry about that when iterating for ranges on any side. You don’t have to worry about whether the iterator is greater than a certain limit or smaller than a certain limit. You can focus on just specifying the range limits and increment value and you’ll get the same results.
Why did I do this?
I came across a problem where I have to iterate over an array in two directions and perform some actions based on one other condition as well. In total, this looks like 4 different methods with all the ranges and boolean checks written separately. I didn’t want to write 4 different methods and I wrote this and just wrote the one method with all the different kinds of parameterization.
4 iterations in the problem.
In the problem, we’ve been given an array and we’ve to find the sum of max(array) — min(array) over all subarrays. After referring to teacher’s resources, we ended up with a solution with involved developing 4 different arrays of information which would help us in getting to the overall sum in O(n) time complexity.
The 4 arrays are as following:
- nearest smaller element on the left side of a certain index.
- nearest smaller element on the right side of a certain index.
- nearest greater element on the left side of a certain index.
- nearest greater element on the right side of a certain index.
Each of these sub problems can be solved in O(n) using a Stack as a helping data structure. The solution depends on which side we iterate from. Satisfying the nearest smaller or nearest larger element is done by another functional parameter which checks if the new element is larger or smaller than the top of the stack and either pops it or leaves it based on the variant that we’re looking at.
int[] nearestSmallerOnLeft = iteration(A, true, true);
int[] nearestGreaterOnLeft = iteration(A, false, true);
int[] nearestSmallerOnRight = iteration(A, true, false);
int[] nearestGreaterOnRight = iteration(A, false, false);private int[] iteration(
int[] A,
boolean smaller,
boolean increasing) {
return iterate(
A,
For.of(0, A.length - 1, increasing ? 1 : -1),
(curr, next) -> smaller ? curr >= next : curr <= next,
increasing ? -1 : A.length);
}private int[] iterate(
int[] A,
For loop,
BiPredicate<Integer, Integer> pop,
int fallback) {
int[] res = new int[A.length];
Stack<Integer> stack = new Stack<>();
for (
int i = loop.start;
loop.end.test(i);
i = loop.next.applyAsInt(i)) {
while (!stack.isEmpty() && pop.test(A[stack.peek()], A[i])) {
stack.pop();
}
res[i] = !stack.isEmpty() ? stack.peek() : fallback;
stack.push(i);
}
return res;
}
I used 2 boolean parameters smaller and increasing to differentiate between all the 4 variants. The inner iterate function takes the loop and pop function to manipulate the stack in the way that we wanted to.
Completing the problem
Once we have the 4 arrays, we can find its contribution by determining in how many subarrays the current index will satisfy the condition. For determining the count of subarrays for a particular index, we’ve to find the possibilities of subarray start indices and subarray end indices and multiply those two. If the count is multiplied by the current element, we’d end up with the contribution of the element at the current index. Iterating this for all the elements will give us a look up solution for the whole array, running in overall O(n) time complexity.
private int overallSum() {
long res = 0;
for (int i = 0; i < A.length; i++) {
long max = subArraysWithCurrent(
nearestGreaterOnLeft[i], i, nearestGreaterOnRight[i]);
long min = subArraysWithCurrent(
nearestSmallerOnLeft[i], i, nearestSmallerOnRight[i]);
long contribution = ((max - min) * A[i]) % MOD;
res = (res + contribution) % MOD;
res = (res + MOD) % MOD;
}
return (int) res;
}private long subArraysWithCurrent(
long leftExclusive,
long current,
long rightExclusive) {
return (current - leftExclusive) * (rightExclusive - current);
}
The core iterate function is fairly small and we can surely write 4 different copies of that but that would reduce it’s maintainability and doing that would not have given me the chance to develop a construct that I’m really proud of.
Full working solution
This is me presenting another quick technique if you’re looking for different types of iterations and are struggling with writing entangled code. One aspect that I’ve mentioned yet is that by creating this For class, we’ve separated the for loop structure and it’s limits reducing complexity that may arise with the syntax if you regularly iterate over a range of numbers.
Adios! Keep Learning!
