This is a little discussion/example of design for modularity and re-use, inspired by javaAddict and Orlando Augusto posts in their thread “Dynamic Multidimensional Array Printing” https://www.daniweb.com/programming/software-development/code/305580/dynamic-multidimensional-array-printing

That thread has 3 solutions to printing the contents of a multi-dimensional array of arbitrary dimensions - although in fact all the solutions will work for any structure of arrays and scalars within arrays, regardless of shape or size.

But really there are two things going on here

  1. recursively traverse all the elements within the arbitrarily nested arrays or scalars
  2. print the contents with nice layout/indentation.

I think it’s worth the extra effort to separate those two things, and thus generate simpler code, with greater opportunities for code re-use. The model I will use is the same as NIO’s Files.walkFileTree. It’s known as the Visitor Pattern, and many UML parsers use it as well. You have one class that handles traversing (“walking”) the data structure, calling methods in a second class (“Visitor”) for each thing it finds.

In this case the Visitor is

public interface Visitor {

    // called at the start of each array, passing its depth (0 for top level)
    void arrayStart(int depth);

    // called for each element in each array, 
    // areMoreElements is true if this is not the last element in this array
    void element(Object element, boolean areMoreElements);

    // called at the end of each array
    void arrayEnd();
}

So a trivial example of an implementation would be

class TrivialPrinter implements Visitor {

    @Override
    public void arrayStart(int depth) {
        System.out.print("[");
    }

    @Override
    public void element(Object element, boolean areMoreElements) {
        System.out.print(element);
        if (areMoreElements) {
            System.out.print(", ");
        }
    }

    @Override
    public void arrayEnd() {
        System.out.print("]");
    }

}

The walker has a constructor that takes the Visitor as a parameter, and one public method public void walk(Object nestedArrays), e.g.

   new ArrayWalker(new TrivialPrinter()).walk(obj2);

In effect this creates a pluggable print formatter, that separates the slightly tacky code needed to indent properly from the slightly tacky code that walks the arrays. Here’s a Visitor that indents nicely:

class IndentedPrinter implements Visitor {

private String indent = "";
private boolean afterElements = false;

@Override
public void arrayStart(int depth) {
    if (indent.length() >= 0) {
        System.out.println();
    }
    System.out.print(indent + "[");
    indent += "  ";
}

@Override
public void element(Object element, boolean isMore) {
    System.out.print(element);
    if (isMore) {
        System.out.print(", ");
    }
    afterElements = true;
}

@Override
public void arrayEnd() {
    indent = indent.substring(2);
    if (afterElements) {
        System.out.print("]");
    } else {
        System.out.println();
        System.out.print(indent + "]");
    }
    afterElements = false;
}

}

If you don’t like that formatting, just write another Visitor.

But wait (as Jobs used to say) there’s more thing…

the Walker can be used for all kinds of uses depending on the Visitor, e.g.

class Analyser implements Visitor {

@Override
public void arrayStart(int depth) {}

@Override
public void element(Object element, boolean areMoreElements) {
    // look for largest / smallest / some specified element
   // accumulate statistics - sum / count / average etc
}

@Override
public void arrayEnd() {}

}

Or, you could write a similar walker but for arbitrarily nested Collections, but still use the same visitor to do the formatted printing.

The complete runnable code is attached, so comments please?
JC

Edited 3 Weeks Ago by JamesCherrill

Comments
Nice code!
class ArrayWalker {

    //  methods that walker calls as it walks the nested arrays
    public interface Visitor {

        // called at the start of each array, passing its depth (zero for top level)
        void arrayStart(int depth);

        // called for each element in each array, 
        // areMoreElements is true if this is not the last element in this array
        void element(Object element, boolean areMoreElements);

        // called at the end of each array
        void arrayEnd();
    }

    // creates a walker using a specified Visitpr
    public ArrayWalker(Visitor visitor) {
        this.visitor = visitor;
    }

    // walks through every element in every array in strict top-down, left-right order
    // calls the visitor's methods as it goes
    public void walk(Object nestedArrays) {
        walkRecursive(nestedArrays, 0, false);
    }

    private final Visitor visitor;

    private void walkRecursive(Object element, int depth, boolean areMoreElements) {

        if (element == null || !element.getClass().isArray()) {
            visitor.element(element, areMoreElements);
            return;
        }
        visitor.arrayStart(depth);
        int length = java.lang.reflect.Array.getLength(element);
        for (int i = 0; i < length; i++) {
            Object sub = java.lang.reflect.Array.get(element, i);
            walkRecursive(sub, depth + 1, i != (length - 1));
        }
        visitor.arrayEnd();
    }

}

class TrivialPrinter implements ArrayWalker.Visitor {

    @Override
    public void arrayStart(int depth) {
        System.out.print("[");
    }

    @Override
    public void element(Object element, boolean areMoreElements) {
        System.out.print(element);
        if (areMoreElements) {
            System.out.print(", ");
        }
    }

    @Override
    public void arrayEnd() {
        System.out.print("]");
    }

}

class IndentedPrinter implements ArrayWalker.Visitor {

    private String indent = "";
    private boolean afterElements = false;

    @Override
    public void arrayStart(int depth) {
        if (indent.length() >= 0) {
            System.out.println();
        }
        System.out.print(indent + "[");
        indent += "  ";
    }

    @Override
    public void element(Object element, boolean isMore) {
        System.out.print(element);
        if (isMore) {
            System.out.print(", ");
        }
        afterElements = true;
    }

    @Override
    public void arrayEnd() {
        indent = indent.substring(2);
        if (afterElements) {
            System.out.print("]");
        } else {
            System.out.println();
            System.out.print(indent + "]");
        }
        afterElements = false;
    }

}

class NestedArrayPrintDemo {

    public static void main(String[] args) {

        int[][][] obj2 = {{{5, 4, 2, 9}, {1, 2, 3, 4}, {4, 3, 2, 1}},
        {{50, 40, 20, 90}, {10, 20, 30, 40}, {40, 30, 20, 10}}};
		
        new ArrayWalker(new TrivialPrinter()).walk(obj2);
        new ArrayWalker(new IndentedPrinter()).walk(obj2);
    }

}

Or, you could write a similar walker but for arbitrarily nested Collections

Is there a difference between your "walker" and an "iterator"? "Walk", "traverse", "iterate", these seem like synonyms. Just thinking about naming conventions and a standard way of doing things. I note that you are not using/extending any official Java implementing classes or interfaces in your code (ie creating a NestedArray class that extends ArrayList or extending Iterator/Iterable). Is this something you could use with an actual official Java class like LinkedList or TreeNode as opposed to your nested array that isn't official? I'm particularly interested in taking a tree or linked list, a tree especially, and having it "print" as XML or in such a way that it could be used for something like Graphviz' dot option (tree printout below). I imagine in that case you would create a TreeWalker class with a TreeWalker.Visitor interface and then write DotPrinter and XMLPrinter classes, each of which would implement TreeWalker.Visitor?

digraph
{
    node1[label="5"]
    node2[label="6"]
    node3[label="7"]
    node4[label="4"]
    node5[label="6"]
    node6[label="9"]
    node7[label="4"]
    node1->{node2,node3}
    node2->{node4,node5}
    node3->{node6,node7}
}

Edited 3 Weeks Ago by AssertNull

Hi
Yes, those terms are pretty synonymous - I just followed the NIO file walker style. I think it implies a 2D structure, where the others are more a 1D thing? Java 8's forEach() methods are the simplest possible walker/visitor and are functionaly equivalent to an Iterator, but the visitor style is called a "passive iterator" as opposed to the traditional "active iterator" (ref).
The nested arrays stuff is because I was following on from an earier thread that was about nested arrays. Personally I can't think of a use case for arbitrarily nested arrays, but that's not the point; it's just a sufficiently complicated 2D structure. You may have noticed that I didn't bother to discuss how the nested array walker works.
It's a fundamental reason for using this pattern that it works for all kinds of nested structures (flies/directories, XML, trees in general etc). So yes, the Walker is specific to the internals of the structure, the Visitor is specific to the output format desired. The clever bit is defining the Visitor interface to be sufficiently general but not too complex.
The file tree walker tutorial discusses an excellent example of a real-world complex application.
https://docs.oracle.com/javase/tutorial/essential/io/walk.html

Edited 3 Weeks Ago by JamesCherrill

Comments
Good stuff. Thanks.

I once wrote an alternative code to using the visitor pattern for this in the python language. See this snippet Generic non recursive tree traversal. I'm using it quite often, and it is very practical. This python version uses generators, which is a kind of coroutine, but I think it would be relatively easy to write a java version using iterators. Also the code is a little complex because it can walk DAGs and not only trees.

The input in java would be a root node (in your case, nodes are arrays or array elements) and an iterator factory, which would return for each node an iterator over its children. The output would be an iterator which would change the state of a "path" instance at every step. This path represents a path in the tree from the root node to the current node being visited.

One advantage of this design over the visitor pattern is that the calling code controls the traversal at every step. For example, the traversal can be stopped when a certain condition is met. The other thing is that you don't need to write visitor instances, instead you write iterator instances, which I think is a more reusable item.

I whish I knew Java well enough to port my snippet to Java. I may try to write a python version using java-like iterators one day or the other :)

One advantage of this design over the visitor pattern is that the calling code controls the traversal at every step

Right there is the interesting distinction between passive and active iteration. Yes, there are many cases where you want to control the iteration process, but there are others where you just want to process all the data without needing to think about how it is iterated. I think there are use cases for both strategies.
Stopping a passive iteration, eg when doing a search, is usually implemented by the Visitor methods returning a continue/stop boolean.

In Java you could cover pretty much every combination of all the standard nestable containers by programming the Walker for arrays, Collections and Trees. The Collections would be implemented via their Iterators. You get a couple of 3-way if blocks, but nothing too horrible. Anyway, the whole point is that once written you never need to look at the internals of the Walker again. If anyone is interested I can hack that together pretty quickly. Trees are a bit different because you may want a different Visitor API. For arrays and Collections you just need to know when you are starting a new one, and how deep it is nested, but for Trees you may want a List of the parents of the current element.

The Visitor can also be simplified using Java 8 lambdas and interface default methods, but I thought that is really a different topic.

Edited 3 Weeks Ago by JamesCherrill

Following the previous post, here's a replacement version of the Walker's recursive method that handles all Java's Collection types (lists, sets etc) as well as arrays in any combination.

    private void walkRecursive(Object element, int depth, boolean areMoreElements) {

        if (element == null) {
            return;
        }

        if (element.getClass().isArray()) {
            visitor.arrayStart(depth);
            int length = java.lang.reflect.Array.getLength(element);
            for (int i = 0; i < length; i++) {
                Object sub = java.lang.reflect.Array.get(element, i);
                walkRecursive(sub, depth + 1, i != (length - 1));
            }
            visitor.arrayEnd();
            return;
        }

       if (element instanceof Iterable) { // all Collections are Iterable
            visitor.arrayStart(depth);
            Iterator it = ((Iterable) element).iterator();
            while (it.hasNext()) {
                walkRecursive(it.next(), depth + 1, it.hasNext());
            }
            visitor.arrayEnd();
            return;
        }

       // not array or iterable, assume not a container
        visitor.element(element, areMoreElements);

    }

(in which case we need to think of a better name for the start/endArray methods!)

Edited 3 Weeks Ago by JamesCherrill

Comments
Cool man!
The article starter has earned a lot of community kudos, and such articles offer a bounty for quality replies.