Form a tree parent -childs from String

[Srikkanth Mohanasundaram]

Hello all,

I have a list of strings which is sorted and looks something like this

Test>
Test>A
Test>A>B
Test>A>D
Test>A>D>E
Test>C

Test1>
Test1>X
Test1>Y

I need to create a tree structure which would help me to loop through the values easily. I though of creating a bean which contains the parent name and list of children.But i am stuck on how to populate the bean and on how to retrieve the values if i am going to have a list of beans.

Thanks,
Srikkanth

[Rahul P Kumar]

Think of trie algoritm.

[David Newton]

What code do you have so far?

[Srikkanth Mohanasundaram]

This is the tree model which i have in mind.

  
public class TestModel {
	TestModel parent = null;
	String name;
	List children;

	public TestModel(String name) {
		this.parent = null;
		this.name=name;
		this.children = new ArrayList();
	}

	public String getName() {
		return name;
	}

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

	public List getChildren() {
		return children;
	}

	public void setChildren(List children) {
		this.children = children;
	}

	public void addChildNode(TestModel child) {
		child.parent = this;
		if (!children.contains(child))
			children.add(child);
	}

	/**
	 * remove node from tree
	 */
	public void remove() {
		if (parent != null) {
			parent.removeChild(this);
		}
	}
	/**
	 * remove child node
	  */
	private void removeChild(TestModel child) {
		if (children.contains(child))
			children.remove(child);

	}
	public String toString() {
		// TODO Auto-generated method stub
		return this.name+" children "+this.children;
	}
	
	

}
 

I'm really stuck on looping through the string and populating the model.

  public class Test2 {
	public static void main(String[] args) {
	List li=new ArrayList();
	li.add("Test>");	
        li.add("Test>A");
        li.add("Test>A>B");
        li.add("Test>A>D");
        li.add("Test>A>D>E");
        li.add("Test>C");
        li.add("Test1>");
        li.add("Test1>X");
        li.add("Test1>Y");
 
	Collections.sort(li);
	System.out.println(li);
	
	TestModel m=new TestModel("tree");
	for(int i=0;i<li.size();i++)
	{
		String path=(String)li.get(i);
		String[] all=path.split(">");		
		if(all.length==1)
                {
		TestModel level1=new TestModel(all[0]);
		m.addChildNode(level1);	
                }
		
		// How do i do for deeper level?
	}
	System.out.println(m);
	}
	
}  

[David Newton]

I would think that recursively descending the tree to find the appropriate parent would be a good first step.

[Srikkanth Mohanasundaram]

David Newton wrote:I would think that recursively descending the tree to find the appropriate parent would be a good first step.

Thanks David.I'll try and let you know

[Rahul P Kumar]

Adding everything from root to last leaf in the list will soon start getting big. with each new number of new leaf or stem. This way you are storing things repeatedly

[Srikkanth Mohanasundaram]

Rahul.p Kumar wrote:Adding everything from root to last leaf in the list will soon start getting big. with each new number of new leaf or stem. This way you are storing things repeatedly

Sorry I don't get you.I'm not trying to store the values repeatedly. I'm trying to create a tree of the TestModel objects

Thanks,
Srikkanth

[Rahul P Kumar]

when you say

# li.add("Test>A");
# li.add("Test>A>B");
# li.add("Test>A>D");
# li.add("Test>A>D>E");
# li.add("Test>C");
# li.add("Test1>");
# li.add("Test1>X");
# li.add("Test1>Y");

aren't you storing Test as many times, then A 4 times and so on....

[David Newton]

Only if he's doing it wrong.

[Srikkanth Mohanasundaram]

No that is the list of strings which is the input for me to create the Tree.
Hope i'm making myself clear.

Thanks,
Srikkanth

[Rahul P Kumar]

so first time Test comes, you store, next time Test>A comes, you store both Test and A in original format, isn't it?

[Srikkanth Mohanasundaram]

Yes you are right.

[Rahul P Kumar]

why can't you try a nested hashmap datastructure, as I earlier mentioned.

[Srikkanth Mohanasundaram]

Hello Rahul,
I cannot use a HashMap i guess.I feel the data structure i have will do the job, but I'm having problems building the tree with list of Strings stuck on adding the children recursively.

Thanks,
Srikkanth

[David Newton]

What you have will work just fine (although I'd also use a map--but that's more a matter of preference).

Where are you stuck? What have you tried so far?

[Rahul P Kumar]

while adding childNode, you are checking contains(), which uses equals(), so make sure you have overridden equals() and hence hashcode() as well

[Rahul P Kumar]

you want to do probably like this:
at top "tree" is there. it has then a list of objects Test and Test1. Each of which has further List of objects, say Test has list of objects A and B. So nexst time an input like Test>A>C comes, first enquire list of "tree" at top. If it has Test, then further enquire in same fashion, as soon as it says it does not have that element, from there on start adding the elements.

[Srikkanth Mohanasundaram]

  public class Test2 {
	public static void main(String[] args) {
	List li=new ArrayList();
	li.add("Test>");	
 li.add("Test>A");
 li.add("Test>A>B");
 li.add("Test>A>D");
 li.add("Test>A>D>E");
 li.add("Test>C");
 li.add("Test1>");
 li.add("Test1>X");
 li.add("Test1>Y");

 
	Collections.sort(li);
	System.out.println(li);
	
	TestModel m=new TestModel("tree");
	for(int i=0;i<li.size();i++)
	{
		String path=(String)li.get(i);
		String[] all=path.split(">");		
		
		TestModel level1=new TestModel(all[all.length-1]);			
		TestModel model=findParent(m,path);		
		model.addChildNode(level1);
		
	}
	System.out.println(m);
	}
	
	
	static TestModel findParent(TestModel m,String path)
	{
		String[] paths=path.split(">");
		List childs=m.getChildren();
		System.out.println(childs);
		if(childs.size()>0)
		{
			for(int i=0;i<childs.size();i++)
			{
			TestModel childModel=(TestModel)childs.get(i);
			if(paths.length==1)
			{
				if(paths[0].equals(childModel.name))
				{
					return m;
				}
			}
			else{
				findParent(childModel,path.substring(0,path.indexOf(">")));
			}
			}
			
		}
		
		
		return m;
	}
}  

What I'm trying to do is to create a TestModel for each String in the list and then find the parent so that it can be added to the child nodes.But for some reason it is always adding to the root node.

David and Rahul,
Thanks for all your time

P.S If i get the the findParent method working, I guess it will work fine.What do you think?

Thanks,
Srikkanth

[Srikkanth Mohanasundaram]

Here is an update to the same code findParent method

   
static TestModel findParent(TestModel m,String path)
	{
		String[] paths=path.split(">");
		//System.out.println("findParent "+m.name);
		List childs=m.getChildren();
		//System.out.println(childs);
		if(childs.size()>0)
		{
			for(int i=0;i<childs.size();i++)
			{
			TestModel childModel=(TestModel)childs.get(i);
			//System.out.println("child model "+childModel.getName());
			//System.out.println(path);
			System.out.println(paths.length);
			if(paths.length==1)
			{
				System.out.println("paths  "+path);
				if(paths[0].equals(childModel.name))
				{
					return m;
				}
			}
			else{
				System.out.println("here");
				System.out.println(path.substring(0,path.lastIndexOf(">")));
				m=findParent(childModel,path.substring(0,path.lastIndexOf(">"))+">");
			}
			}
			
		}
		
		//System.out.println(m);
		return m;
	}

 

So, now have the tree created but only for two levels.

Leaf D is attached to node B,when in fact it should have gone into A.

Thanks,
Srikkanth

[David Newton]

Recursion is often tricky--I usually recommend "playing computer": trace out the algorithm manually, with a paper and pencil, in order to figure stuff like this out.

[Srikkanth Mohanasundaram]

David Newton wrote:Recursion is often tricky--I usually recommend "playing computer": trace out the algorithm manually, with a paper and pencil, in order to figure stuff like this out.

Did exactly that to get the recursion right. Thanks David.Thanks Rahul

Srikkanth