In solving this problem: http://www.cs.duke.edu/csed/newapt/drawtree.html I wrote the code below but it seems to run too slow. Is there a faster way of checking all of the child nodes w/o using a FOR loop? Would a queue be helpful?
public class DrawTree {
HashMap<String, ArrayList<String>> map =
new HashMap<String, ArrayList<String>>();
ArrayList<String> drawing = new ArrayList<String>();
String root;
public String[] draw(int[] parents, String[] names) {
for(int x=0; x<parents.length; x++)
{
int parentindex = parents[x];
//root name
if(parentindex==-1)
{
root=names[x];
if(!map.containsKey(names[x]))
{
map.put(names[x], new ArrayList<String>());
}
continue;
}
//add parent, child to map
if (!map.containsKey(names[parentindex]))
map.put(names[parentindex],
new ArrayList<String>());
map.get(names[parentindex]).add(names[x]);
}
sketch("",root,false);
return drawing.toArray(new String[drawing.size()]);
}
//***IMPROVE RUN TIME - different algorithm??***
//method takes root and prefix?
public void sketch(String parent, String child, boolean addPipe){
StringBuilder toAdd = new StringBuilder();
//don't need to add connector pipe
if(!addPipe)
{
//number of spaces to add to prefix
int spaces = parent.indexOf('-')+1;
//add spaces to prefix
while(spaces>0)
{
toAdd.append(" ");
spaces--;
}
toAdd.append("+-"+child);
}
//index of pipe in parent, -1 if parent doesn't have pipe
int parentPipe = parent.indexOf('|');
//need to add connector pipe & parent has pipe
// (is a child of a subtree)
if(parentPipe>0)
{
//number of spaces to add to prefix
int spaces = parent.indexOf('-')+1;
//add spaces to prefix
while(spaces>0)
{
if(spaces==parentPipe) toAdd.append('|');
else toAdd.append(" ");
spaces--;
}
toAdd.append("+-"+child);
}
//need to add pipe and parent doesn't have pipe
if(addPipe && parentPipe<0)
{
int spaces = parent.indexOf('-')+1;
while(spaces>0)
{
if(spaces==2) toAdd.append('|');
else toAdd.append(" ");
}
toAdd.append("+-"+child);
}
//add child to list of tree drawing
String node = toAdd.toString();
drawing.add(node);
//System.out.println(node);
//loop through list of children, passing each recursively
//...count level?
if(map.containsKey(child))
{
//System.out.println("map works");
for(int x = 0; x<map.get(child).size(); x++)
{
boolean pipe = false;
if(x<(map.get(child).size()-1)) pipe=true;
//System.out.println(map.get(child).get(x));
sketch(node, map.get(child).get(x), pipe);
}
}
}