java - Overflowing issue when allocating tree nodes -


i'm working on problem requires me generate n-ary tree based on given vertex pairs, read in input file. current node class:

public class node<t> {     private int idx;     private int data;     private node<t> parent;     private list<node<t>> children;      // template new nodes     public node() {         this.idx = 1;         this.data = 0;         this.parent = null;         this.children = new arraylist<node<t>>();     }      public void insertnode(node<t> currnode, int leftidx, int rightidx) {         if (currnode.idx == leftidx) {             node<t> childnode = new node<t>();             childnode.idx = rightidx;             childnode.parent = currnode;             currnode.children.add(childnode);                         return;         }          (int = 0; < currnode.children.size(); i++) {             node<t> tempnode = currnode.children.get(i);             if (tempnode.idx == leftidx ) {                 node<t> childnode = new node<t>();                 childnode.idx = rightidx;                 childnode.parent = tempnode;                 tempnode.children.add(childnode);                             return;             }         }          node<t> upcurrnode = currnode.children.get(currnode.children.size() - 1);         upcurrnode.insertnode(upcurrnode, leftidx, rightidx);         return;     }           }  

as can see, insertnode method being called recursively, in order populate whole tree nodes, no data. there additional methods adding values these nodes well, input file split 2 parts - creating nodes first, performing queries update data inside each node later (i have no control on this).

i ran 2 input files, 1 around 1 hundred nodes within tree, other 2 orders of magnitude larger. smaller tree works fine, got following error upon testing larger tree, occurs after ~2050th recursive call:

node: exception in thread "main" java.lang.stackoverflowerror         @ sun.nio.cs.singlebyte.withresult(unknown source)         @ sun.nio.cs.singlebyte.access$000(unknown source)         @ sun.nio.cs.singlebyte$encoder.encodearrayloop(unknown source)         @ sun.nio.cs.singlebyte$encoder.encodeloop(unknown source)         @ java.nio.charset.charsetencoder.encode(unknown source)         @ sun.nio.cs.streamencoder.implwrite(unknown source)         @ sun.nio.cs.streamencoder.write(unknown source)         @ java.io.outputstreamwriter.write(unknown source)         @ java.io.bufferedwriter.flushbuffer(unknown source)         @ java.io.printstream.write(unknown source)         @ java.io.printstream.print(unknown source)         @ java.io.printstream.append(unknown source)         @ java.io.printstream.append(unknown source)         @ java.util.formatter$formatspecifier.print(unknown source)         @ java.util.formatter$formatspecifier.print(unknown source)         @ java.util.formatter$formatspecifier.printinteger(unknown source)         @ java.util.formatter$formatspecifier.print(unknown source)         @ java.util.formatter.format(unknown source)         @ java.io.printstream.format(unknown source)         @ node.node.insertnode(node.java:38)         @ node.node.insertnode(node.java:44)         @ node.node.insertnode(node.java:44)         @ node.node.insertnode(node.java:44)         @ node.node.insertnode(node.java:44)         @ node.node.insertnode(node.java:44)...         (repeats couple thousand lines) 

line 38 system.out.format("node: %d parent: %d\n", childnode.idx, childnode.parent.idx); while line 34 recursive insertnode call: upcurrnode.insertnode(upcurrnode, leftidx, rightidx);.

my best guess on issue program overflows default memory allocation jvm, based on thrown stackoverflowerror exception. understandably, can see memory overhead each node quite high: 4 bytes idx field, 4 data, 4 reference parent node, , 40 bytes + whatever amount arraylist needs overhead creating default 1 children. assuming total memory required per each node ~70kb, bigger tree's total size around 700mb, beyond ridiculous such simple program (i wrong, way; see comment below).

so, question is: insertnode method inefficient? there way optimize such can handle large amount of data, without requiring person running program pass special flag allows increased memory usage? thank you

edit: here's code snippet on how tree first generated:

node<integer> tree = new node<integer>();   string line = null; // line reader // temp variables processing nodes during tree generation int leftnodeidx, rightnodeidx;  // string array processing node indexes string[] twonodesidx; // first line number of nodes     int numn = integer.parseint( bufferedreader.readline() );  // populate tree child nodes specified in input_file  (int = 0; < (numn - 1); i++) {     line = bufferedreader.readline();     twonodesidx = line.split("\\s");     leftnodeidx = integer.parseint(twonodesidx[0]);     rightnodeidx = integer.parseint(twonodesidx[1]);     tree.insertnode(tree, leftnodeidx, rightnodeidx); } 


Comments

Popular posts from this blog

java - nested exception is org.hibernate.exception.SQLGrammarException: could not extract ResultSet Hibernate+SpringMVC -

sql - Postgresql tables exists, but getting "relation does not exist" when querying -

asp.net mvc - breakpoint on javascript in CSHTML? -