Introducing the Zipper data structure – Arrays, collections and data structures

115. Introducing the Zipper data structure

The Zipper data structure is meant to facilitate cursor-like navigation capabilities over another data structure such as a tree. Moreover, it may provide capabilities for manipulating the tree like adding nodes, removing nodes, and so on.The Zipper is created on the top of a tree and it is characterized by the current position of the cursor and the current range or the current visibility area. At any moment, the Zipper doesn’t see or act on the entire tree; its actions are available only on a subtree or a range of the tree which is relative to the current position. The modification accomplished via the Zipper is visible only in this range, not in the entire tree.In order to navigate and determine the current range, a Zipper must be aware of the tree structure. For instance, it must be aware of all the children of each node and this is why we start from an interface that must be implemented by any tree that wants to take advantage of a Zipper:

public interface Zippable {
  public Collection<? extends Zippable> getChildren();
}

A tree that implements Zippable ensures that it exposes its children to the Zipper. For instance, a tree Node implementation can be done as follows:

public class Node implements Zippable {
  private final String name;
  private final List<Node> children;
  public Node(final String name, final Node… children) {
    this.name = name;
    this.children = new LinkedList<>(Arrays.asList(children));
  }
  public String getName() {
    return name;
  }
  @Override
  public Collection<Node> getChildren() {
    return this.children;
  }
  @Override
  public String toString() {
    return “Node{” + “name=” + name
      + “, children=” + children + ‘}’;
  }      
}

The following figure reveals the Zipper characteristics at some moment in time:

Figure 2.26 – The Zipper position and range on an arbitrary tree

The Zipper’s current position is represented by the node labeled 55 – the zipper cursor is on position 55. The highlighted gray area is the zipper’s current range/visibility. Everything that happens in this area is invisible outside of it. From the current position the Zipper can move down(), up(), left(), and right(). Every move will refine the Zipper range accordingly.When the Zipper is applied to a tree, each node of the tree (Node) becomes a Zipper-node represented here by the ZipNode class. As you can see in the following code, a ZipNode acts as a wrapper of a Node and it represents the unit of work for the Zipper:

public final class ZipNode<T extends Zippable>
     implements Zippable {
  private static final Zippable[] DUMMY = new Zippable[0];
  private final T node;        // wrap the original tree node
  private Zippable[] children; // list of children
  // wrap a ZipNode without children  
  protected ZipNode(final T node) {
    this(node, DUMMY);
  }
 
  // wrap a ZipNode and its children   
  protected ZipNode(final T node, Zippable[] children) {
    if (children == null) {
      children = new Zippable[0];
        }
    this.node = node;
    this.children = children;
  }