Solved

# Walk down a hierarchy - recursion

Posted on 2004-11-04
481 Views
Here is my problem.

I have a method that returns an array:

Ie:

Object[] myArr = heirarchy.getAllChildren();

I need to figure out how to walk a complete heirarcy with this method.

could someone give me an example of a recursive method that walks down a heirarchy (an array of objects that could have arrays of objects associated with them)

Thanks

0
Question by:zerium

LVL 86

Expert Comment

Why does it return Object[]? What is the real type involved?
0

LVL 2

Author Comment

here is the real method:

Channel[] channels = channel.getAllSubchannels();
0

LVL 86

Expert Comment

Then it would be something like:

public void walkHierarchy(Channel[] channels) {
for(int i = 0;i < channels.length;i++) {
if (channels[i].hasSubchannels()) {
walkHierarchy(channels[i].getSubchannels());
}
else {
// do something with channels[i]
}

}

}
0

LVL 86

Expert Comment

>>walkHierarchy(channels[i].getSubchannels());

should have been

walkHierarchy(channels[i].getAllSubchannels());
0

LVL 2

Author Comment

ok i have that working:

however I need to create an xml type hierarchy too...

public void walkHierarchy(Channel[] channels)
throws ApplicationException, ValidationException, IOException{
for(int i = 0;i < channels.length;i++)
{
String channelName = channels[i].getName();
if (channels[i].getSubchannelCount() != 0)
{
walkHierarchy(channels[i].getAllSubchannels());
}
System.out.println("<node>" + channelName + "</node>");// do something with channels[i]

}

}

how do i keep track of which level i'm on?
0

LVL 13

Expert Comment

or like this:

public  Collection getAllChildren(Object rootNode)
{
Collection children = new Vector();

Iterator firstLevel = getFirstLevelChildren(rootNode);
while( firstLevel.hasNext() )
{
Object child = firstLevel.next();
}
return children;
}

and then:
Collection children = heirarchy.getAllChildren(root);
Object[] myArr = children.toArray();
0

LVL 13

Expert Comment

correction!! sorry like this

public  Collection getAllChildren(Object rootNode)
{
Collection children = new Vector();

Iterator firstLevel = getFirstLevelChildren(rootNode);
while( firstLevel.hasNext() )
{
Object child = firstLevel.next();
}
return children;
}

and then:
Collection children = heirarchy.getAllChildren(root);
Object[] myArr = children.toArray();
0

LVL 2

Author Comment

petmagdy, I'm sorry I'm not getting your example... or at least how to adapt it into my code.

I am getting hung up on the line:

Iterator firstLevel = getFirstLevelChildren(rootNode);

0

LVL 13

Expert Comment

ok this funtion will retrieve only the first children level to clarify it more it can be like this:

Collection firstLevel = getFirstLevelChildren(rootNode);
Iterator itr = firstLevel.iterator();
while( itr.hasNext() )
{
Object child = itr.next();
........
}

i am using classes in package java.util.*;

tell me if still something vague
0

LVL 6

Expert Comment

if it is just to parse xml do not implement your own parser use e.g. xerces... all methods you need are already there..

see e.g. www.cafeconleche.org
0

LVL 2

Author Comment

im lost on the method "getFirstLevelChildren(rootNode)"

is that something i have to write?

mightyone, I'm not trying to parse xml I'm trying to create a hierarchy of xml out of something that isn't xml.
0

LVL 13

Expert Comment

yes u have to write this, i was assuming any hierarchy struture not neccessary xml, i noticed xml lately, this function will retrieve the first level children of the parent object
0

LVL 2

Author Comment

so it needs to return a collection?
0

LVL 13

Expert Comment

collection or any object based on collection like Vector or List
0

LVL 2

Author Comment

ok, does the vector need to contain all of my channels?

I have this bit of code that is feeding this whole heirarchy:

Channel[] channels = channel.getAllSubchannels();

which only gets the sub channels for the level that you are on...

so should i do this?:

Vector firstLevel= new Vector();

0

LVL 2

Author Comment

I have to head home for the day I'll get back to you all tomorrow
0

LVL 13

Expert Comment

yes u can but but getAllSubchannels() must take as a parameter the parent it must look like:

Channel[] channels = channel.getAllSubchannels(parent);

or otherwise the recursive function (getAllChildren(Object rootNode)) will recurse for ever and cause stack overflow
)
0

LVL 6

Expert Comment

0

LVL 2

Author Comment

the heirarchy is built in a content management system and the channels are navigation.

so their might be any given number of subchannels on any given channel. However there is always one root "Home" which has a method getAllSubchannels() which accepts no parameter. This method has been handed to me in the compiled code and I cannot alter it.

The getAllSubchannels() method returns an array of Channel objects so what I need is a method that will recursively travel the chain and get the name of each channel and create a heirarchical xml document.

the method for getting the name is .getName()
0

LVL 13

Expert Comment

and for a single Channel Object what can u get? can u get the subchannels of this channel?
0

LVL 13

Expert Comment

if u have this API for example Channel.getChannelSubChannels() then u code will look like this:

public  Collection getAllChildren()
{
Collection children = new Vector();
Collection firstLevelChildren = getAllSubchannels();
Iterator firstLevel = firstLevelChildren.iterator();
while( firstLevel.hasNext() )
{
Object child = firstLevel.next();
}
return children;
}

public  Collection getChannelAllChildren(Object channel)
{
Collection children = new Vector();
Collection firstLevelChildren = channel.getChannelSubChannels() ;
Iterator firstLevel = firstLevelChildren.iterator();
while( firstLevel.hasNext() )
{
Object child = firstLevel.next();
}
return children;
}

0

LVL 2

Author Comment

yes for any channel object you can call getAllSubchannels()

there is also a utility metod that is channel.getSubchannelCount() which returns the number of subchannels for a given channel
0

LVL 13

Expert Comment

then u have :) look at my last comment just replace Object channel  with Channel channel and getChannelSubChannels() with getAllSubchannels()
0

LVL 2

Author Comment

ok I made the change and here are my exceptions:

the method below isn't being invoked on an object:

Collection firstLevelChildren = getAllSubchannels();

Incompatible types - found Channel[] required Collection:
Collection firstLevelChildren = channel.getAllSubchannels() ;

getChannelAllChildren(Channel) cannot be applied to java.lang.Object

Also can you show me how you would call these methods?
0

LVL 13

Expert Comment

I was showing schematics no exact code, but u can do this:
First import java.util.*;

then

List firstLevelChildren = Arrays.asList( getAllSubchannels() );

also replace Object channel with Channel channel in all code

0

LVL 13

Expert Comment

sorry zerium, one correction:

Vector firstLevelChildren = (Vector) Arrays.asList( getAllSubchannels() );
0

LVL 2

Author Comment

thanks for walking me through this...

I still have these problems: (commented below)

I am calling the method this way:

Collection children = getChannelAllChildren(site.getHomeChannel());

public  Collection getAllChildren()
throws ApplicationException, ValidationException, IOException{
Collection children = new Vector();
//cannot resolve method:
Collection firstLevelChildren = getAllSubchannels();
Iterator firstLevel = firstLevelChildren.iterator();
while( firstLevel.hasNext() )
{
//Incompatible types Found: 'java.lang.Object', required 'Channel':
Channel child = firstLevel.next();
}
return children;
}

public  Collection getChannelAllChildren(Channel channel)
throws ApplicationException, ValidationException, IOException{
Collection children = new Vector();
Vector firstLevelChildren = (Vector) Arrays.asList( channel.getAllSubchannels() );
Iterator firstLevel = firstLevelChildren.iterator();
while( firstLevel.hasNext() )
{
//Incompatible types Found: 'java.lang.Object', required 'Channel':
Channel child = firstLevel.next();
}
return children;
}
0

LVL 13

Expert Comment

//Incompatible types Found: 'java.lang.Object', required 'Channel':
Channel child = firstLevel.next();
to be:
Channel child = (Channel) firstLevel.next();
0

LVL 2

Author Comment

duh... i should have caught that cast...

how about the method that is trying to be called in getAllChildren()?

this line:

what object should getAllSubChannels() be invoked on? should the channel object be passed into getAllChildren?

Collection firstLevelChildren = getAllSubchannels();
0

LVL 13

Expert Comment

I don't know the signature of Method getAllSubchannels() u know it

but the call in the first function should be called on the home, i suppose will be:

Vector firstLevelChildren = (Vector) Array.asList( home.getAllSubchannels() );
0

LVL 13

Expert Comment

Zerium is ur home of type Channel too? if soo u may not need the first metthod getAllChildren()!
u will only use the second method getChannelAllChildren() and call at as u did:

Collection children = getChannelAllChildren(site.getHomeChannel());

0

LVL 2

Author Comment

yeah i was wondering about that...

now all i need to do is loop through the collection and rebuild the heirarchy. its not throwing any errors.
0

LVL 13

Expert Comment

I don't under stand >> rebuild the heirarchy
0

LVL 2

Author Comment

well i have the collection and now i have to loop over it and build out the structure

ie:

Nav Item one
>Sub Item one
>Sub Item two
Nav Item three
>Sub Item one
>Sub Item one

etc.
0

LVL 13

Accepted Solution

yes, now u acheived ur objective to do the recursive transverse through ur hierarchy
0

LVL 2

Author Comment

I'm trying to figure out the best way to do that should I open another question? I can up the points to this one if you can help
0

LVL 2

Author Comment

I got it figured out (building the path) thanks petmagdy your code worked really well and now I have a nice array to work with.
0

## Featured Post

### Suggested Solutions

Introduction This article is the first of three articles that explain why and how the Experts Exchange QA Team does test automation for our web site. This article explains our test automation goals. Then rationale is given for the tools we use to aâ€¦
Introduction This article is the second of three articles that explain why and how the Experts Exchange QA Team does test automation for our web site. This article covers the basic installation and configuration of the test automation tools used byâ€¦
This video teaches viewers about errors in exception handling.
This tutorial explains how to use the VisualVM tool for the Java platform application. This video goes into detail on the Threads, Sampler, and Profiler tabs.