Wednesday, December 12, 2012

Breaking Nested Loops in Java

Recently I was very surprised by the fact that even experienced Java developers may not know how to break nested loops effectively in Java. Probably that’s because the usage of this language feature is relatively rare. Indeed if you have a deeply nested loop then it would be better to rework the code and introduce a couple of additional methods to divide the original one into easily conceivable parts. Occasionally though you do need to use nested loops and in that case it’s good to know the most effective ways to leverage them.

Assume you have a task to print the first negative element of the matrix represented by a two-dimensional array. The example is contrived a bit, but it allows illustrating the idea. I can’t even remember how many times I saw people writing the code like this to do it:
public class BreakNestedLoopsExample {
    public static void main(String[] args) {
        int[][] m = {
                {1,  2,  3},
                {4,  5,  6},
                {7, -8,  9},
        };

        for (int i = 0; i < m.length; ++i) {
            boolean isFound = false;
            
            for (int j = 0; j < m[i].length; ++j) {
                if (m[i][j] < 0) {
                    System.out.printf("m[%d][%d] = %d", i, j, m[i][j]);
                    isFound = true;
                    break;
                }
            }
            
            if (isFound) {
                break;
            }
        }                
    }
}
This code compiles and works correctly but it is awkward. A better solution exists - labeled break statement:
public class BreakNestedLoopsExample {
    public static void main(String[] args) {
        int[][] m = {
                {1,  2,  3},
                {4,  5,  6},
                {7, -8,  9},
        };
        
        OUTER_LOOP:
        for (int i = 0; i < m.length; ++i) {
            for (int j = 0; j < m[i].length; ++j) {
                if (m[i][j] < 0) {
                    System.out.printf("m[%d][%d] = %d", i, j, m[i][j]);
                    break OUTER_LOOP;
                }
            }
        }
    }
}
Usually break statement is applied to the innermost loop. But in this case the label on line 9 and a labeled break statement on line 14 allow breaking the outer loop from within nested loop easily. This code looks much cleaner and avoids the usage of isFound local variable whose only purpose is to break the outer loop if a negative element is found.

The same approach can be used with continue statement. I will use contrived but illustrative example again. Assume you have a three-dimensional array to represent an array of matrices and you want to find the indices of all matrices which have at least one negative element. You can do it using something like this:
public class ContinueNestedLoopsExample {
    public static void main(String[] args) {
        int[][][] m = {
            {
                {0,  7,  2},
                {1, -5,  3},
                {4,  2,  2},
            },                
            {
                {1,  2,  3},
                {4,  5,  6},
                {7,  8,  9},                    
            },
            {
                {6, -2,  3},
                {4,  3,  6},
                {1,  0,  5},
            }
        };

        List<Integer> indices = new ArrayList<Integer>();

        OUTER_LOOP:
        for (int i = 0; i < m.length; ++i) {
            for (int j = 0; j < m[i].length; ++j) {
                for (int k = 0; k < m[i][j].length; ++k) {
                    if (m[i][j][k] < 0) {
                        indices.add(i);
                        continue OUTER_LOOP;
                    }
                }
            }
        }

        System.out.println(indices);
    } 
}
This program will print the following output:

[0, 2]

Obviously the same result can be achieved by rewriting the nested loop in terms of break statement:
public class ContinueNestedLoopsExample {
    public static void main(String[] args) {
        int[][][] m = {
            {
                {0,  7,  2},
                {1, -5,  3},
                {4,  2,  2},
            },                
            {
                {1,  2,  3},
                {4,  5,  6},
                {7,  8,  9},                    
            },
            {
                {6, -2,  3},
                {4,  3,  6},
                {1,  0,  5},
            }
        };

        List<Integer> indices = new ArrayList<Integer>();

        for (int i = 0; i < m.length; ++i) {
            MATRIX_LOOP:
            for (int j = 0; j < m[i].length; ++j) {
                for (int k = 0; k < m[i][j].length; ++k) {
                    if (m[i][j][k] < 0) {
                        indices.add(i);
                        break MATRIX_LOOP;
                    }
                }
            }
        }

        System.out.println(indices);
    }
}
Which labeled statement to use is a matter of personal taste and a particular task in hand, but any of them is certainly better than using clunky isFound-style.

Thanks for reading,
See you soon!

2 comments:

  1. This is great thanks a lot for sharing this blog. i am looking for such type of information to my best knowledge and i get through this blog so i am very happy and thankful to you that you are providing the great information ..... thank you very much .....


    Web Development Company

    ReplyDelete