sorting a hierarchy of objects
1 posts in topic
Flat View  Flat View
TOPIC ACTIONS:
 

Posted By:   Michael_Kane
Posted On:   Monday, December 30, 2002 01:38 PM

I'm working on a movie-info web application which includes genre information in the form of objects from the genre() class I created. Each genre() object has a name, genreID and parentID. Ideally, this system will allow me to recreate the hierarchy of genres and subgenres by figuring out which genres are siblings, which have a parent-child relationship, etc. The problem I'm having is in sorting these unordered genres so they can be laid out onscreen in a tree format. I'm working on the administrative screens for this movie application now, and I want the user to easily see the structure of the genres and their children. So far, I have a function that pulls ALL genres from the database, then adds   More>>

I'm working on a movie-info web application which includes genre information in the form of objects from the genre() class I created.



Each genre() object has a name, genreID and parentID. Ideally, this system will allow me to recreate the hierarchy of genres and subgenres by figuring out which genres are siblings, which have a parent-child relationship, etc.



The problem I'm having is in sorting these unordered genres so they can be laid out onscreen in a tree format. I'm working on the administrative screens for this movie application now, and I want the user to easily see the structure of the genres and their children.



So far, I have a function that pulls ALL genres from the database, then adds them to a new Vector in the order they should be seen. Basically, there's a FOR loop that says, "pull one genre - IF it has a child, pull that genre next, ELSE look for a sibling genre, ELSE look for an
'uncle' genre."



This method seems to make sense, but I'm having a difficult time trying to find 'uncle' genres. I assume this kind of sorting problem is not new, so if anyone has a better way to handle this, I'd love to hear it.



Thanks very much



Michael Kane

   <<Less

Re: sorting a hierarchy of objects

Posted By:   Stephen_McConnell  
Posted On:   Wednesday, January 1, 2003 06:11 AM

Unfortunately, java has not done much in the way of Data Structures for the type of Tree you are looking for in the Collections API's. They have implemented TreeSet and TreeMap, but those are binary (red-black) trees.


I guess by "uncle" you mean elements on the same "tree level". This is not really that hard if you understand the "breadth first search" algorithms in tree structures. I once adapted it for nodes with multiple children (for a Graph Data Structure). What I would look at is instead of placing the nodes in a Vector, look at the methods in the javax.swing.tree.DefaultTreeModel API's for creating the tree. Since you want to display the tree visually, this puts you half way there using the javax.swing.tree.* classes.


As you add elements to the tree, you would look for the parent to add the node to the tree. A breadth first traversal of the tree would allow you to find "uncles" since you keep all the nodes on the same level in a Queue.


For online discussions of Data Structures check out the link provided.


Hope this helps; and gives you some direction. What you are doing is not a trivial problem, but it is fun and rewarding.


Stephen McConnell

About | Sitemap | Contact