Java Iterable inheritance

Question

Before all, here is a Minimal Working Example of my code on GitHub: https://github.com/rmwesley/DancingLinks_MWE

I've been trying to implement the Dancing Links' algorithm by D. Knuth to solve the Exact Cover problem.

The code works. Problem is, I want to implement an Iterator. In fact, the Iterator works for Node.java. But not for Column.java, as I will further detail. I've tried completely refactoring the code and doing some crazy modifications, but to no avail. I left some of my best trials as commented lines of code. These were the least garbagey ones.

My current design is as follows: Given a problem matrix, I aimed at constructing the main data structure with 4-way nodes. So first I implemented Node.java, a 4-way circularly linked data structure. Then I extend Node.java in Column.java, which is the "backbone" of the structure. Column elements then make up the main row. Rows of Nodes are then linked with the rest of the structure with .addRow(). That is, new rows come below the last added row and above the column. Remember, circular. See the schematics in D. Knuth's paper: https://arxiv.org/abs/cs/0011047. With this, the full structure can be initialized from a given problem matrix. "this" in Column serves as the head itself, so no elements are added above or below it.

Here is my source code: Node.java

public class Node implements Iterable<Node> {
    private Node upNode;
    private Node downNode;
    private Node leftNode;
    private Node rightNode;
    private Column column;

    public Node() {
        upNode = this;
        downNode = this;
        leftNode = this;
        rightNode = this;
        column = null;
    }

    @Override
    public String toString() {
        String str = this.column.getSize() + " ";
        for (Node node : this){
            str += node.column.getSize() + " ";
        }
        return str;
    }

    @Override
    public java.util.Iterator<Node> iterator(){
        Node currNode = this;
        return new NodeIter(this);
    }

    public Column getColumn(){
        return this.column;
    }

    public void setColumn(Column column){
        this.column = column;
    }

    public Node getR(){
        return this.rightNode;
    }

    public Node getD(){
        return this.downNode;
    }

    public Node getL(){
        return this.leftNode;
    }

    public Node getU(){
        return this.upNode;
    }

    void removeHoriz() {
        this.rightNode.leftNode = this.leftNode;
        this.leftNode.rightNode = this.rightNode;
    }

    void removeVert() {
        this.downNode.upNode = this.upNode;
        this.upNode.downNode = this.downNode;
    }
    
    void restoreVert() {
        this.downNode.upNode = this;
        this.upNode.downNode = this;
    }

    void restoreHoriz() {
        this.rightNode.leftNode = this;
        this.leftNode.rightNode = this;
    }

    //Create an horizontal link between nodes
    public void linkD(Node other) {
        this.downNode = other;
        other.upNode = this;
    }

    //Create a vertical link between nodes
    public void linkR(Node other) {
        this.rightNode = other;
        other.leftNode = this;
    }
    void addHoriz(Node other) {
        other.rightNode = this.rightNode;
        other.leftNode = this;
    }

    void addVert(Node other) {
        other.downNode = this.downNode;
        other.upNode = this;
    }
}

Column.java

import java.util.HashSet;
import java.util.Iterator;
import java.util.NoSuchElementException;

//public class Column extends Node implements Iterable<Column>{
public class Column extends Node {
    private int size;
    private String name;

    public Column() {
        super();
        this.setColumn(this);
        size = 0;
        name = new String();
    }

    public Column(int length) {
        this();
        Column currColumn = this;
        for(int i = 0; i < length; i++){
            currColumn.setName("" + i);

            Column nextColumn = new Column();
            currColumn.linkR(nextColumn);
            currColumn = nextColumn;
        }
        currColumn.linkR(this);
    }

    public void addRow(int[] vector) throws Exception {
        Column currColumn = this;
        Node firstNode = new Node();
        Node currNode = firstNode;
        Node prevNode = currNode;

        for(int index=0; index < vector.length; index++){
            currColumn = currColumn.getR();
            if(vector[index] == 0) continue;

            currColumn.increment();
            currColumn.getU().linkD(currNode);
            currNode.linkD(currColumn);
            currNode.setColumn(currColumn);

            prevNode = currNode;
            currNode = new Node();
            prevNode.linkR(currNode);
        }
        currColumn = currColumn.getR();
        prevNode.linkR(firstNode);
        if(currColumn != this){
            throw new Exception("Differ in length");
        }
    }
    public Column(int[][] matrix) throws Exception {
        this(matrix[0].length);
        for(int i = 0; i < matrix.length; i++){
            this.addRow(matrix[i]);
        }
    }

    @Override
    public Column getR(){
        return (Column) super.getR();
    }

    @Override
    public Column getL(){
        return (Column) super.getL();
    }

    @Override
    public String toString(){
        String str = "";

        //for (Column currColumn : this) str += currColumn.getSize() + " ";
        for (Column currColumn = this.getR();
                currColumn != this;
                currColumn = currColumn.getR()){
            str += currColumn.getSize() + " ";
        }
        return str;
    }

    public String getName(){
        return this.name;
    }

    public int getSize(){
        return this.size;
    }

    public void setSize(int size){
        this.size = size;
    }

    public void setName(String name){
        this.name = name;
    }

    public void increment(){
        this.size++;
    }

    public void decrement(){
        this.size--;
    }

    /*
    @Override
    public Iterator<Column> iterator(){
        return new Iterator<Column>(){
            private Column currNode = Column.this;

            @Override
            public boolean hasNext(){
                return currNode.getR() != Column.this;
            }
            @Override
            public Column next(){
                if (!hasNext()) throw new NoSuchElementException();
                currNode = currNode.getR();
                return currNode;
            }
        };
    }
    */
}

NodeIter.java

public class NodeIter implements java.util.Iterator<Node>{
    private Node head;
    private Node current;

    public NodeIter(Node node){
        this.head = this.current = node;
    }

    @Override
    public boolean hasNext(){
        return current.getR() != head;
    }
    @Override
    public Node next(){
        if (!hasNext()) throw new java.util.NoSuchElementException();
        current = current.getR();
        return current;
    }
}

Commented lines give these errors when uncommented:

src/Column.java:5: error: Iterable cannot be inherited with different arguments: <Column> and <Node>
public class Column extends Node implements Iterable<Column>{
       ^
src/Column.java:111: error: iterator() in Column cannot implement iterator() in Iterable
    public Iterator<Column> iterator(){
                            ^
  return type Iterator<Column> is not compatible with Iterator<Node>
  where T is a type-variable:
    T extends Object declared in interface Iterable
src/Column.java:76: error: incompatible types: Node cannot be converted to Column
        for (Column currColumn : this) str += currColumn.getSize() + " ";

How do I make Column.java iterable?

I've been coding in Java recently, but without carefully considering design patterns. So I fully believe I am suffering the consequences of bad code design. Should I make some abstract class or make use of some Generic Type? Like Node and Column, just so I can implement Iterable. Am I wrong? Does anyone have any pointers?

Tried using generics and overriding .iterator() method with different return types in Column.java. Even tried using completely different class structures.

Answer 1

The Node class has an implementation of the Iterable interface in the form of one method:

@Override
public java.util.Iterator<Node> iterator(){
    Node currNode = this;
    return new NodeIter(this);
}

(BTW the first line of this method is not doing anything useful)

You are trying to make Node's subclass Column implement Iterable, meaning you want to add an overriding method like this:

@Override
public Iterator<Column> iterator()

Such an override which only differs in return type is not allowed in Java, hence the compilation error.

The fundamental problem is that, since Node is an Iterable, all its subclasses will also be an Iterable due to inheritance.

I guess you would like to write code like this:

for(Node n : node) {
    for(Column c : n.getColumn()) {
        c.increment();
    }
}

Currently I think you could do this:

for(Node n : node) {
    for(Node c : n.getColumn()) {
        ((Column) c).increment();
    }
}

Where you are casting the iterand to Column in order to access Column methods.

I do think the design is weird when I read this for instance:

public Column() {
    super();
    this.setColumn(this);

eh? So a Column is a Node which has a column field? Seems like the design is conflicted about whether a Column is-a Node, or a Node has-a Column... I feel like your iterable problem will magically disappear once you figure that out.

EDIT: I don't fully grasp the algorithm and data structure yet (although I read a bit about it). From what I've understood I think you should create something like the following structure:

class Matrix {
    Column[] columns;
    Matrix(int[][] input) {
        // init Columns
    }
}

class Column {
    String name;
    int size;
    Node firstNode;
}

class Node {
    Node up;
    Node down;
    Node left;
    Node right;
}

And avoid sub classing, it's usually not needed. Better to work with interfaces and collaborators.