通过非递归函数发生的stackoverflow异常

Stackoverflow exception that occurs through non-recursive function

我对 Java 泛型比较陌生,下面两个泛型 class 表示图形数据结构中涉及的顶点和连接器。

Connector.java class

package ac.lk.iit.algorithmscomplexities.coursework2.datastructure;
public class Connector<E,F> {
    private Vertex<E, F> start, end;    // starting Vertex instance and ending Vertex instance of the Connector
    private F element;  // the data of generic type F to be held by the Vertex connector
    private double value;   // a descriptive value of the connector relative to other connectors depending on the scenario

    /**
     * a protected constructor which creates an instance of Connector class
     * @param start starting Vertex instance of the Connector
     * @param end ending Vertex instance of the Connector
     * @param element data of generic type F to be held by the Vertex connector
     * @param cost descriptive value of the connector relative to other connectors depending on the scenario
     */
    protected Connector(Vertex<E,F> start, Vertex<E,F> end, F element, double cost) {
        this.setStart(start);
        this.setEnd(end);
        this.setElement(element);
        this.setValue(cost);
    }

    /**
     * returns the starting Vertex instance of the Connector
     * @return the starting Vertex instance of the Connector
     */
    protected Vertex<E,F> getStart() {
        return start;
    }

    /**
     * sets the Vertex argument provided to the starting Vertex instance field of the Connector instance
     * @param start the starting Vertex instance of the Connector
     */
    private void setStart(Vertex<E,F> start) {
        if(start != null) {
            this.start = start;
        }
    }

    /**
     * returns the ending Vertex instance of the Connector
     * @return the ending Vertex instance of the Connector
     */
    protected Vertex<E,F> getEnd() {
        return end;
    }

    /**
     * sets the Vertex argument provided to the ending Vertex instance field of the Connector instance
     * @param end the ending Vertex instance of the Connector
     */
    private void setEnd(Vertex<E,F> end) {
        if(end != null) {
            this.end = end;
        }
    }

    /**
     * returns the data of generic type F held by the Vertex connector
     * @return the data of generic type F held by the Vertex connector
     */
    protected F getElement() {
        return element;
    }

    /**
     * sets the data of generic type F to the element instance field of the Vertex connector
     * @param element data of generic type F to be held by the Vertex connector
     */
    private void setElement(F element) {
        if(element != null) {
            this.element = element;
        }
    }

    /**
     * returns a descriptive value of the connector relative to other connectors depending on the scenario
     * @return descriptive value of the connector relative to other connectors depending on the scenario
     */
    protected double getValue() {
        return value;
    }

    /**
     * sets a descriptive value of the connector relative to other connectors depending on the scenario to value instance field of Connector instance
     * @param value a descriptive value of the connector relative to other connectors depending on the scenario
     */
    private void setValue(double value) {
        if(value >= 0) {
            this.value = value;
        }
    }

    public String toString() {
        return this.element.toString();
    }

    @SuppressWarnings("unchecked")
    @Override
    public boolean equals(Object object) {
        if(object instanceof Connector) {
            Connector<E,F> newConnector = (Connector<E, F>)object;
            // since it is a directed graph the start, end of each connector and the data element should be unique
            return ((this.getStart().equals(newConnector.getStart())) && (this.getEnd().equals(newConnector.getEnd())) && (this.getElement().equals(newConnector.getElement())));
        }
        else {
            return false;
        }
    }
}

Vertex.java class

package ac.lk.iit.algorithmscomplexities.coursework2.datastructure;
import java.util.LinkedList;
public class Vertex<E,F> {

    private int id;         // a unique id value for each vertex created
    private E dataElement;  // data to be held within a vertex
    private LinkedList<Connector<E, F>> pointers;   // list of references to other Vertices connected

    // keeps track of the number of vertices created during the runtime
    protected static int NUMBER_OF_VERTICES = 0;

    /**
     * a protected constructor which creates an instance of Vertex class with the generic E argument provided
     * @param element the element of generic type E to be assigned to dataElement instance field
     */
    protected Vertex(E element) {
        this.setId(Vertex.NUMBER_OF_VERTICES);
        Vertex.NUMBER_OF_VERTICES++;
        this.setDataElement(element);
        this.pointers = new LinkedList<Connector<E, F>>();
    }

    /**
     * returns the unique Integer id value of the Vertex instance
     * @return the unique Integer id value of the Vertex instance
     */
    protected int getId() {
        return id;
    }

    /**
     * sets the Integer argument provided to the id instance field of the Vertex instance
     * @param id the Integer argument provided to be set to the id instance field of the Vertex instance
     */
    private void setId(int id) {
        if(!(id < 0)) {
            this.id = id;
        }
    }

    /**
     * returns the content of the dataElement instance field of the Vertex instance 
     * @return the content of the dataElement instance field of the Vertex instance
     */
    protected E getDataElement() {
        return dataElement;
    }

    /**
     * sets the argument of generic type E to the dataElement instance field of the Vertex instance
     * @param dataElement the element of generic type E to be assigned to dataElement instance field
     */
    protected void setDataElement(E dataElement) {
        if(dataElement != null) {
            this.dataElement = dataElement;
        }
    }

    /**
     * returns the list of Connector instances associated with a Vertex instance
     * @return the list of Connector instances associated with a Vertex instance
     */
    protected LinkedList<Connector<E, F>> getPointers() {
        return pointers;
    }

    /**
     * adds a new Connector instance starting from this Vertex and ending in the specified Vertex instance
     * @param another the ending Vertex of the Connector
     * @param element the data element of generic type F held by the Connector
     * @param value the list of Connector instances associated with a Vertex instance
     */
    protected void connectTo(Vertex<E,F> another, F element, double value) {
        Connector<E,F> newConnector = new Connector<E,F>(this, another, element, value);

        if(!(this.pointers.contains(newConnector))) {
            this.pointers.add(newConnector);
        }

        LinkedList<Connector<E, F>> anotherList = another.getPointers();
        if(!(anotherList.contains(newConnector))) {
            anotherList.add(newConnector);
        }

        System.out.println("[this vertex]:" + this.pointers);
        System.out.println("[that vertex]:" + another.pointers);
    }

    @SuppressWarnings("unchecked")
    @Override
    public boolean equals(Object object) {

        if(object instanceof Vertex) {
            Vertex<E,F> newVertex = (Vertex<E,F>) object;
            if(this.pointers.size() != newVertex.getPointers().size()) {
                return false;
            }
            if(!(this.getDataElement().equals(newVertex.getDataElement()))) {
                return false;
            }
            for(int i = 0 ; i < this.pointers.size() ; i++) {
                if(!(this.pointers.get(i).equals(newVertex.getPointers().get(i)))) {
                    return false;
                }
            }
        }
        else {
            return false;
        }
        return true;

    }

    public static void main(String[] args) {
        Vertex<String, String> vertex1 = new Vertex<String, String>("Chiranga");
        Vertex<String, String> vertex2 = new Vertex<String, String>("Robin");
        Vertex<String, String> vertex3 = new Vertex<String, String>("Sunethra");
        Vertex<String, String> vertex4 = new Vertex<String, String>("Ananda");

        vertex1.connectTo(vertex2, "John", 0);
        //vertex1.connectTo(vertex3, "Mark", 0);

        //vertex1.connectTo(vertex4, "Rob", 0);

        vertex2.connectTo(vertex3, "James", 0);

        vertex4.connectTo(vertex2, "John", 0);
        vertex4.connectTo(vertex3, "Sean", 0);

        //System.out.println(vertex1.equals(vertex4));
        //System.out.println(vertex1.equals(vertex2));
    }
}

上面的classes在执行下面的代码段时会抛出一个Whosebugexception。

vertex4.connectTo(vertex3, "Sean", 0);

很难理解上述异常背后的真正原因,因为我没有涉及任何递归代码示例,而且它发生在我仅在某些 Vertex 实例之间建立连接时。大多数与上述异常类型相关的代码问题都在讲递归,但上面的似乎有所不同。

为什么我总是得到提到的 Whosebug 异常?

请注意,上面涉及 main 方法的代码示例是为测试目的而编写的。

查看堆栈跟踪,很容易理解问题出在哪里:

Exception in thread "main" java.lang.WhosebugError
    at ac.lk.iit.algorithmscomplexities.coursework2.datastructure.Connector.equals(Connector.java:123)
    at ac.lk.iit.algorithmscomplexities.coursework2.datastructure.Vertex.equals(Vertex.java:117)
    at ac.lk.iit.algorithmscomplexities.coursework2.datastructure.Connector.equals(Connector.java:123)
    at ac.lk.iit.algorithmscomplexities.coursework2.datastructure.Vertex.equals(Vertex.java:117)
    at ac.lk.iit.algorithmscomplexities.coursework2.datastructure.Connector.equals(Connector.java:123)
    ...

你的Connectorequals方法调用Vertexequals方法,后者调用Connectorequals方法,...

equals Vertex class 的方法包含:

if(!(this.pointers.get(i).equals(newVertex.getPointers().get(i))))

其中 this.pointers.get(i)Connector,因此 Vertex 中的 equals 调用 Connector 中的 equals

equalsConnector class 包含:

return ((this.getStart().equals(newConnector.getStart())) && (this.getEnd().equals(newConnector.getEnd())) && (this.getElement().equals(newConnector.getElement())));

并且由于 getStart()getEnd() 属于 Vertex 类型,这意味着 Connectorequals 正在调用 equalsVertex.

因此 VertexConnectorequals 的调用可能会导致无限递归。

你的 equals 方法...

当您在 connectTo 中执行 contains 方法时,它会调用连接器上的 equals 以确定连接器是否在列表中。

连接器的 equals 方法:

@SuppressWarnings("unchecked")
@Override
public boolean equals(Object object) {
    if (object instanceof Connector) {
        Connector<E, F> newConnector = (Connector<E, F>) object;
        // since it is a directed graph the start, end of each connector and the data element should be unique
        return ((this.getStart().equals(newConnector.getStart())) && (this.getEnd().equals(newConnector.getEnd())) && (this.getElement().equals(newConnector.getElement())));
    } else {
        return false;
    }
}

注意它是如何对 getStart() 进行比较的 - 这是一个顶点。那么顶点等于:

@SuppressWarnings("unchecked")
@Override
public boolean equals(Object object) {

    if (object instanceof Vertex) {
        Vertex<E, F> newVertex = (Vertex<E, F>) object;
        if (this.pointers.size() != newVertex.getPointers().size()) {
            return false;
        }
        if (!(this.getDataElement().equals(newVertex.getDataElement()))) {
            return false;
        }
        for (int i = 0; i < this.pointers.size(); i++) {
            if (!(this.pointers.get(i).equals(newVertex.getPointers().get(i)))) {
                return false;
            }
        }
    } else {
        return false;
    }
    return true;

}

所以顶点等于:在 this.pointers(连接器)上调用等于。

换句话说,您的 equals 方法具有循环依赖性 - 它们各自调用另一个 equals 方法,因此您会得到堆栈溢出异常。