CODEWITHSUNDEEP
javaandroidmemoryarrayliststack-overflow
yesbutmaybeno
yesbutmaybeno

Reputation: 1148

How to solve StackOverflowError with nested ArrayLists?

I'm running my project on some Android devices, and I'm getting errors that I think have to do with nested ArrayLists.

Here's the basic setup - I have a figure made up of limbs (think of them as nodes). Each node can have more children nodes and so on and so on. So, each Node class has a member ArrayList<Node> childrenNodes containing any number of children Nodes.

I can't exactly pinpoint why things go wrong, but after adding ~220 nodes in succession to each other (essentially creating a long string of connected nodes), the app crashes.

E/AndroidRuntime(9299): FATAL EXCEPTION: GLThread 674
E/AndroidRuntime(9299): Process: __, PID: 9299
E/AndroidRuntime(9299): java.lang.StackOverflowError
E/AndroidRuntime(9299): at __.Node.getSelectedNode(Node.java:283)
E/AndroidRuntime(9299): at __.Node.getSelectedNode(Node.java:273)
E/AndroidRuntime(9299): at __.Node.getSelectedNode(Node.java:273)
E/AndroidRuntime(9299): at __.Node.getSelectedNode(Node.java:273)
...etc

The function Node::getSelectedNode iterates down the tree of nodes, originating from the main node, to find which one is being clicked, it looks like this (stripped of unrelated code):

public Node getSelectedNode(float x, float y)
{
    Node node = null;

    // First look through children (look at front-most child first, the last one).
    // ---------------------------------------------------------------------------
    for (int i = _childrenNodes.size() - 1; i >= 0; --i)
    {
        node = _childrenNodes.get(i).getSelectedNode(x, y);

        if (node != null)
            break;
    }

    // If still not found, check this node.
    // ------------------------------------
    if (node == null)
    {
        // if (this node is being clicked) {
        node = this;
    }

    return node;
}

So I guess when I call this function, the Stack gets filled up with a ton of calls to getSelectedNode() depending on the number of descendents a node has, leading to a StackOverflowError?

Is that right? If so, I really don't know how to go about fixing this, should I not be using an ArrayList?

Any advice appreciated!

Edit: Here's another scenario I've found that causes a StackOverflowError, when I clone one of these figures (which essentially iterates through each of the Nodes and clones them). Again, the issue seems to originate from a Node with too many levels of children, grandchildren, etc...

I'm also 99% sure there are no cycles, as I've tested for it, this issue doesn't occur with lower number of nodes, and doesn't happen at all on the desktop (at least not with this amount of nodes, probably more).

public Node(Node parentNodeRef, Node cloneFrom)
{
    // This constructor is used when cloning a Node.
    this._parentNodeRef = parentNodeRef;

    this._x = cloneFrom._x;
    this._y = cloneFrom._y;

    // ...more cloning of members here, etc...
    // this below is the problematic code, if there's too many children of children of children, etc (I got up to about 220) - I get the error

    _childrenNodes = new ArrayList<Node>(cloneFrom._childrenNodes.size());
    for (int i = 0, numChildren = cloneFrom._childrenNodes.size(); i < numChildren; ++i)
        _childrenNodes.add(new Node(this, cloneFrom._childrenNodes.get(i)));
    }
}

Upvotes: 0

Views: 140

Answers (2)

Robin Dijkhof
Robin Dijkhof

Reputation: 19278

The most common cause of stack overflow is excessively deep or infinite recursion. Languages like Scheme, which implement tail-call optimization, allow infinite recursion of a specific sort—tail recursion—to occur without stack overflow. This works because tail-recursion calls do not take up additional stack space.

http://en.wikipedia.org/wiki/Stack_overflow

getSelectedNode calls itself in the forloop, which will call itselg again and again and again...

Upvotes: 0

pseudonym
pseudonym

Reputation: 156

Instead of recursion, use a code defined stack or queue and a while loop. 

queue q = new queue()
q.push(root)
while not q.empty()
      node = q.pop()
      for each child of node
           q.push(child)
      //perform some code on current node

Upvotes: 1

Related Questions