Is There a Java Class for this Kind of Data Structure?

[Hal Vaughan]

I think if I weren't self taught, I'd know the terms to describe what I'm
trying to do and might even know what kind of class to look for in the Java
API. I'm hoping there's a Java class that will do what I need to do. I
think it's some kind of tree structure, but I've only heard the term used
and what I found (like TreeMap) doesn't seem to do what I need. Any info I
find on Trees, though, seems to go back to JTree and I don't need a GUI for
this.

I have a number of data tables and many of them have dependent tables based
on matching certain criteria. These dependent tables often have other
dependent tables. There is no limit to the levels of dependents and to the
number of dependents for each table, but in reality, I doubt any would go
deeper than 5-6 levels.

I have a list of the main tables and each table has its own list of its
immediate dependents (isn't the correct term children?) and, of course,
each child has a list of its own children and so on.

This has worked fine so far, but if a main table is modified, I need to
update all the tables that depend on it, no matter how many levels removed.
There are more details I don't want to go into, but what I'd like to do is
have one structure that a main table has access to that is a list of all
the dependent tables. I can't use a regular list for this because I need
for all the tables at one level to be listed at that level. I was thinking
of something like a LinkedList of LinkedLists.

For instance, the main table would be the first item in the main LinkedList.
The 2nd item would be a LinkedList of all it's children and the 3rd item
would be a another LinkedList of all the grandchilren and so on.

Yes, I can do this with lists of lists, but isn't here some kind of tree or
other kind of branching list that will do this?

Thanks for suggestions!

Hal

 

[Jeff Higgins]

Yes, I can do this with lists of lists, but isn't here some kind of tree
or
other kind of branching list that will do this?

Have you looked at DefaultTreeModel?
Even though it's in the Swing package
it can be used nicely standalone.

 

[Hal Vaughan]

Have you looked at DefaultTreeModel?
Even though it's in the Swing package
it can be used nicely standalone.

Okay. I either missed that or excluded it because it cam up as connected to
Swing. There are two problems that I can see:

1) The root has to be a TreeNode so I'm not clear if I can set a root object
and then add my object as its own root.

2) I don't see a way to add Objects to the tree.

Hal

 

[Bent C Dalager]

Okay. I either missed that or excluded it because it cam up as connected to
Swing. There are two problems that I can see:

1) The root has to be a TreeNode so I'm not clear if I can set a root object
and then add my object as its own root.

I'm not exactly sure what you are saying, but one generally has two
alternatives:

1) Write your own "MyTreeNodeType implements TreeNode" which can, of
course, do whatever you need it to do.

2) Use DefaultMutableTreeNode for the root and put your own object for
that node into the node as a user object (see
DefaultMutableTreeNode.setUserObject).

2) I don't see a way to add Objects to the tree.

You don't add objects to the tree as such. You set a root object in
the tree model's constructor and then you add child objects to this
root object.

Typically, you may use a DefaultMutableTreeNode as the root and also
for all other nodes in the tree. DefaultMutableTreeNode has add(),
children(), etc.

Note that in a TreeModel, there can only be one root object so if you
want multiple roots you will have to make your roots children of the
"real" root and just ignore the real root as much as possible.

Cheers
Bent D

 

[Jeff Higgins]

1) The root has to be a TreeNode so I'm not clear if I can set a root
object
and then add my object as its own root.

2) I don't see a way to add Objects to the tree.

All nodes in DefaultTreeModel are TreeNodes.
DefaultMutableTreeNode wraps an userObject.
You can construct DefaultMutableTreeNode(Object userObject).
Your userObject might be an object that wraps a Table reference
and a Table id or name for example.
Node.getUserObject, Node.setUserObject(), Node.getUserObjectPath() etc.

 

[Jeff Higgins]

As an addition to what Bent said,
You can also extend DefaultMutableTreeNode.
An example that I liked is located here:
<http://www.java2s.com/Code/Java/Swi...theSortTreeModelwithaFilehierarchyasinput.htm>

 

[Oliver Wong]

I think if I weren't self taught, I'd know the terms to describe what I'm
trying to do and might even know what kind of class to look for in the
Java
API. I'm hoping there's a Java class that will do what I need to do. I
think it's some kind of tree structure, but I've only heard the term
used
and what I found (like TreeMap) doesn't seem to do what I need. Any
info I
find on Trees, though, seems to go back to JTree and I don't need a GUI
for
this.

I have a number of data tables and many of them have dependent tables
based
on matching certain criteria. These dependent tables often have other
dependent tables. There is no limit to the levels of dependents and to
the
number of dependents for each table, but in reality, I doubt any would
go
deeper than 5-6 levels.

I have a list of the main tables and each table has its own list of its
immediate dependents (isn't the correct term children?) and, of course,
each child has a list of its own children and so on.

Yes, children is the correct term.

This has worked fine so far, but if a main table is modified, I need to
update all the tables that depend on it, no matter how many levels
removed.
There are more details I don't want to go into, but what I'd like to do
is
have one structure that a main table has access to that is a list of all
the dependent tables. I can't use a regular list for this because I
need
for all the tables at one level to be listed at that level. I was
thinking
of something like a LinkedList of LinkedLists.

In Java, there's an interface called "List", and from the
program-behaviour point of view, it doesn't really matter whether the List
interface is implemented via an ArrayList or a LinkedList or some other
type of List. The term "regular list" is ambiguous and it's unclear what
you are referring to by it (an easy way to clear ambiguity is to post your
source code, since the meaning of the Java language is very precisely
defined -- see http://www.physci.org/codes/sscce.html)

In other words, a LinkedList does not do anything above and beyond
what a plain List can do, so replacing whatever you've got now iwth a
LinkedList is almost guaranteed to not solve your problem.

For instance, the main table would be the first item in the main
LinkedList.
The 2nd item would be a LinkedList of all it's children and the 3rd item
would be a another LinkedList of all the grandchilren and so on.

If the first element of your list is of type "MainTable", and the
second element of your list is of type "LinkedList", then you've got a
heterogenous list, and they're a big pain to work with.

Yes, I can do this with lists of lists, but isn't here some kind of tree
or
other kind of branching list that will do this?

When you wrote...

I have a list of the main tables and each table has its own list of its
immediate dependents (isn't the correct term children?) and, of course,
each child has a list of its own children and so on.

... you demonstrated that you already have a tree implemented. So I
don't think your problem is "how do I add a tree data structure somewhere
in my program?" because you've already done so. I think your problem is
more that you haven't actually identified what your problem is.

You write that you want to "update all the tables that depend on it,
no matter how many levels removed", so why don't you go ahead and do that?
What is it about your current data structure that is preventing you from
being able to write code which does exactly what you want?

- Oliver

 

[Hal Vaughan]

Oliver Wong wrote:

....

When you wrote...


... you demonstrated that you already have a tree implemented. So I
don't think your problem is "how do I add a tree data structure somewhere
in my program?" because you've already done so. I think your problem is
more that you haven't actually identified what your problem is.

You write that you want to "update all the tables that depend on it,
no matter how many levels removed", so why don't you go ahead and do that?
What is it about your current data structure that is preventing you from
being able to write code which does exactly what you want?

First, thanks (to you and everyone else) for a lot of good information.

I did have a method I could call in one table that would step through all
the dependent tables and update them and the Swing components that used
them for setting data, the problem was it was easiest to go through the
list of all dependent tables and for each one call the update, which would
go to that table and do the same. In essence the update would start at the
trunk and follow one branch, then take one fork and so on through to the
end of one branch, then it would back up and go through the next branch.

That worked, or mostly worked, but I found the problem was that tables
several levels down would be updated before some tables only 1 level down
were updated and that would effect what was displayed on the Swing
components. The reason I want to store the tables in a tree is so I can
get more easily make sure I update all tables 1 level down then move to 2
levels down and so on. That way I update all the tables in each level
before moving on to the next level.

From what I can see, there is no way to get all the objects from a tree at
one level. I was considering using the DefaultTreeModel, but that one
issue kept me back. At this point, because I want to go level by level,
I'm thinking of using one list and each item is a list of all the tables at
that level.

Hal

 

[Jeff Higgins]

At this point, because I want to go level by
level,
I'm thinking of using one list and each item is a list of all the tables
at
that level.

This online book was an big help to me
in understanding tree traversals.
<http://www.brpreiss.com/books/opus5/html/book.html>

 

[Oliver Wong]

I did have a method I could call in one table that would step through
all
the dependent tables and update them and the Swing components that used
them for setting data, the problem was it was easiest to go through the
list of all dependent tables and for each one call the update, which
would
go to that table and do the same. In essence the update would start at
the
trunk and follow one branch, then take one fork and so on through to the
end of one branch, then it would back up and go through the next branch.

That worked, or mostly worked, but I found the problem was that tables
several levels down would be updated before some tables only 1 level
down
were updated and that would effect what was displayed on the Swing
components. The reason I want to store the tables in a tree is so I can
get more easily make sure I update all tables 1 level down then move to
2
levels down and so on. That way I update all the tables in each level
before moving on to the next level.

If "ordering" is an issue, see
http://en.wikipedia.org/wiki/Tree_traversal

Note that the problem may also be that your data objects are correctly
being updated, but your GUI is not being updated to reflect the new values
stored in memory.

From what I can see, there is no way to get all the objects from a tree
at
one level. I was considering using the DefaultTreeModel, but that one
issue kept me back. At this point, because I want to go level by level,
I'm thinking of using one list and each item is a list of all the tables
at
that level.

You can do that, but this particular configuration of having a list of
list of elements at a given level doesn't sound like it would be conducive
to writing a recursive algorithm. The usual way to go about it is to take
care of a single node, and then to take care of all of its children. So
rather than working with lists, you'd be working with trees. See
http://en.wikipedia.org/wiki/Recursion

- Oliver

 

[Hal Vaughan]

If "ordering" is an issue, see
http://en.wikipedia.org/wiki/Tree_traversal

Note that the problem may also be that your data objects are correctly
being updated, but your GUI is not being updated to reflect the new values
stored in memory.

That was a problem I think I fixed earlier today. It was tied in to the
fact that my old update would go all the way through one branch and update
the tables, THEN update the components and sometimes the values in the
components were used to figure out the contents of some of the tables.

You can do that, but this particular configuration of having a list of
list of elements at a given level doesn't sound like it would be conducive
to writing a recursive algorithm. The usual way to go about it is to take
care of a single node, and then to take care of all of its children.

That's what I was doing, but then I'd have one branch updated and when
updating the next branch, it would change tables that could effect
components that effected the first branch.

So
rather than working with lists, you'd be working with trees. See
http://en.wikipedia.org/wiki/Recursion

I've got recursion. Actually, I think it's kind of fun!

Hal

 

[Oliver Wong]

Oliver Wong wrote:

[context is working with trees]

That's what I was doing, but then I'd have one branch updated and when
updating the next branch, it would change tables that could effect
components that effected the first branch.

Just to clarify, let's say your tree structure looks like:

A
|- B
|- C
`- D

So "B", "C" and "D" are children of A. Changes to "A" may affect "B",
"C" and "D", so when you update "A", you must also update "B", "C" and
"D".

Are you saying that in addition to this, changes to "B" affect "C" and
"D", so that when you update "B", you must also update "C" and "D" and
vice versa?

- Oliver

 

[Hal Vaughan]

Oliver Wong wrote:

[context is working with trees]

That's what I was doing, but then I'd have one branch updated and when
updating the next branch, it would change tables that could effect
components that effected the first branch.

Just to clarify, let's say your tree structure looks like:

A
|- B
|- C
`- D

More like (and I hate to do diagrams because I know spacing is different on
different fonts):


A
|-+-+
B C D
| |
E F

So "B", "C" and "D" are children of A. Changes to "A" may affect "B",
"C" and "D", so when you update "A", you must also update "B", "C" and
"D".

Are you saying that in addition to this, changes to "B" affect "C" and
"D", so that when you update "B", you must also update "C" and "D" and
vice versa?

It's more like D might provide prompt data to a Swing component that might
effect F just like C does so I have to update C and D at the same time
before E and F are updated. It may just be a different way of drawing the
table, so we may be saying the same thing, but I'm just trying to make sure
we're all saying the same thing. In other words, a table 3 or 4 levels
down could be effected by not 1 but 2 tables at level 2. Theoretically
it's possible it could be effected by more than 2 tables at level 2, but in
practice I would doubt it.

Hal

 

[Oliver Wong]

More like (and I hate to do diagrams because I know spacing is different
on
different fonts):


A
|-+-+
B C D
| |
E F

Who are the children of who in this notation?

[...]

It's more like D might provide prompt data to a Swing component that
might
effect F just like C does so I have to update C and D at the same time
before E and F are updated. It may just be a different way of drawing
the
table, so we may be saying the same thing, but I'm just trying to make
sure
we're all saying the same thing. In other words, a table 3 or 4 levels
down could be effected by not 1 but 2 tables at level 2. Theoretically
it's possible it could be effected by more than 2 tables at level 2, but
in
practice I would doubt it.

I don't have the information I'm looking for, so let me rephrase my
question:

Are tables only affected by their parents, grandparents,
great-grand-parents, etc., or is it possible that they are affected by
uncles/aunts, siblings, etc.

Or to phrase it another way, if you draw a line between a node, and
every node that might affect it, does the line always go towards the root
(which I think is drawn at the top in both our diagrams), or does it
sometimes go up, and then back down?

- Oliver

 

[Hal Vaughan]

Who are the children of who in this notation?

B, C, and D. The grandchildren are E & F.

[...]

It's more like D might provide prompt data to a Swing component that
might
effect F just like C does so I have to update C and D at the same time
before E and F are updated. It may just be a different way of drawing
the
table, so we may be saying the same thing, but I'm just trying to make
sure
we're all saying the same thing. In other words, a table 3 or 4 levels
down could be effected by not 1 but 2 tables at level 2. Theoretically
it's possible it could be effected by more than 2 tables at level 2, but
in
practice I would doubt it.

I don't have the information I'm looking for, so let me rephrase my
question:

Are tables only affected by their parents, grandparents,
great-grand-parents, etc., or is it possible that they are affected by
uncles/aunts, siblings, etc.

They can be affected by uncles/aunts, but NOT by siblings.

Or to phrase it another way, if you draw a line between a node, and
every node that might affect it, does the line always go towards the root
(which I think is drawn at the top in both our diagrams), or does it
sometimes go up, and then back down?

Always goes up, but could go diagonally up.

This is beginning to remind me of early spreadsheets where there were times
you'd need a value in a column way to the right to be used for something
back towards the left and if you had it set for manual recalc, you'd have
to recalc twice to keep it all in sync.

Hal

 

[Oliver Wong]

Oliver Wong wrote:

[talking about trees where the nodes are tables]

They can be affected by uncles/aunts, but NOT by siblings.


Always goes up, but could go diagonally up.

This is beginning to remind me of early spreadsheets where there were
times
you'd need a value in a column way to the right to be used for something
back towards the left and if you had it set for manual recalc, you'd
have
to recalc twice to keep it all in sync.

That is essentially the situation you've got right now. Trees
typically don't lend themselves well to modeling things where uncle/aunt
relationships are important. Are you using the tree structure for other
reasons than this updating-algorithm? If not, you might instead want to
look into using a directed acyclic graph, where each edge in the graph
represents a dependency. That way, when a change in one table occurs, it
can notify all of its dependents (which may be children, nephew/nieces)
who in turn notify their dependents and so on.

Otherwise, if the tree structure is important, you could modify your
updating-algorithm so that it uses a breadth-first traversal instead of a
depth-first traversal. Usually this means making your method
non-recursive, and instead having a queue with a list of nodes that need
to be updated, and you iterate over the queue until it's empty (meaning
all your work is done). A breadth-first traversal means that all the nodes
at level N will be updated before all the nodes at level N+1.

- Oliver

 

[Hal Vaughan]

Oliver Wong wrote:

[talking about trees where the nodes are tables]

They can be affected by uncles/aunts, but NOT by siblings.


Always goes up, but could go diagonally up.

This is beginning to remind me of early spreadsheets where there were
times
you'd need a value in a column way to the right to be used for something
back towards the left and if you had it set for manual recalc, you'd
have
to recalc twice to keep it all in sync.

That is essentially the situation you've got right now. Trees
typically don't lend themselves well to modeling things where uncle/aunt
relationships are important. Are you using the tree structure for other
reasons than this updating-algorithm?

I was looking into a tree because I thought that would be the easiest way to
list all the tables by level or generation and step through them.
Remember, I'm self taught. There have been references in this thread (and
in others when I've asked a question) that have been a huge help to me in
not only answering a question, but in giving me more information about data
structures and algorithms that I did not know. I had a few classes back in
the '70s and '80s in high school and college, but I was not a programming
major and was mostly using Assembler on my Apple //e so a lot of the
concepts in OOP are fairly new to me and I've basically had to learn what I
needed at any particular point in the process. It's a big help when
someone points out what they know are good online resources in this field.
While I find some on my own in Google, often something I think explains a
point well can leave out a lot of info I should know but am unaware of.

If not, you might instead want to
look into using a directed acyclic graph, where each edge in the graph
represents a dependency. That way, when a change in one table occurs, it
can notify all of its dependents (which may be children, nephew/nieces)
who in turn notify their dependents and so on.

Actually, that's part of how I was thinking of using the tree. Whenever the
table data was changed, update() was called and would step through all the
dependent tables. The problem, as I've said, is I didn't have them listed
by level, but just by following a branch.

Otherwise, if the tree structure is important, you could modify your
updating-algorithm so that it uses a breadth-first traversal instead of a
depth-first traversal. Usually this means making your method
non-recursive, and instead having a queue with a list of nodes that need
to be updated, and you iterate over the queue until it's empty (meaning
all your work is done). A breadth-first traversal means that all the nodes
at level N will be updated before all the nodes at level N+1.

Right now I'm experimenting with a loop that I wouldn't actually label as
recursive but is close. It starts with a table, makes that table the first
node in the list, then the loop starts. It gets the children of that table
and makes a list with them as nodes and that new sublist becomes the next
node in the main list. Then it looks at all the grandchild tables and
makes another sublist of them and that becomes the 3rd node on the main
list. I end up with a main list and each node is a sublist. The first
sublist is only 1 item long, containing the initial table. The 2nd
node/sublist is all the children, the 3rd node/sublist is the grandchildren
and so on.

I looked into it several ways since I don't like writing a loop to gather
data, then another to go through that same data, but found if I tried one
loop to process, there were times I'd have to step back one level, so I
decided to list it all. The only actual recursion at this point is getting
a list of tables from one table, then doing the same from each table in the
list.

Hal

 

[Roedy Green]

Thanks for suggestions!

have a look at javax.swing.tree.DefaultTreeModel.

I have not looked closely, but it may be suitable for non-GUI use too.

To roll your own tree is not very difficult. Your Node class has a
ArrayList of child Nodes.. You create the obvious methods to add a
child, remove a child, create a node, chase depth first and breadth
first with the Visitor pattern.

Then to use, you extend the Node Class with extra fields.

If you rarely have new children, you can use an array of children, and
replace it whenever the number of children changes.

You also have a pointer from child to parent.

TreeModel defines a basic interface to a tree.

 

[Oliver Wong]

I was looking into a tree because I thought that would be the easiest
way to
list all the tables by level or generation and step through them.
Remember, I'm self taught.

Picking the right data structure for a given problem is one of those
things you just acquire through experience, I think. It's difficult for me
to say for sure, because I don't know what you're doing with your tables,
but based on what I heard so far, an acyclic directed graph sounds like
the the data structure I'd used to model the dependencies between your
tables.

Presumably, your program is trying to "do something": model global
warming, schedule airplane flights, track inventory in a warehouse, etc.
This "thing" that it is trying to do exists independently of your program;
that is, you could do it manually if you needed to, but it might be
painful, boring, repetitive, etc. This "thing" that is independent of your
program is your "problem domain".

So what I'm wondering is whether the entities in your problem domain
naturally have a tree-like structure to them. If so, then it might be
worth it to stick with trees in your program that reflect the structure of
the problem domain, and use the queue-based algorithm mentioned below.
Otherwise, it might be worth chucking the trees in favour of the acyclic
directed graph (http://en.wikipedia.org/wiki/Acyclic_directed_graph).

A "directed graph" basically means that edges between nodes have
directions associated with them. Here's a non-directed graph:

a---b----c
| |
| |
+--------+

And here's a directed graph:

a-->b<-->c
| ^
| |
+--------+

An acyclic directed graph is simply a direct graph in which there are no
cycles. Or to put it another way, it's a graph in which when you follow
the directions of the arrows, no matter where you start, it's impossible
to end up in the same location you've been to previously.

The above directed graph is not acyclic, because you can start at C, then
go to B, then go to C again. If you make this minor change, the graph
becomes an acyclic one:

a-->b<---c
| ^
| |
+--------+

From A, you can go to B or C. At B, you're stuck. And C, you can only go
to B. There's no way for you to visit a node twice while following the
edges.

Actually, that's part of how I was thinking of using the tree. Whenever
the
table data was changed, update() was called and would step through all
the
dependent tables. The problem, as I've said, is I didn't have them
listed
by level, but just by following a branch.

Dependencies are usually best modelled as an acyclic graph. To take
your earlier example, with nodes A, B, C, D, E, F, G, the graph would look
like:

,-<-B<-.
E<-\ / \
*-<-*---<-C<---*-<-A
F<-/ \ /
`-<-D<-'

That is, A has 3 edges, one pointing to B, one pointing to C and one
pointing to D. B, C and D each have 2 edges, one pointing to E, and one
pointing to F.

When you do your updates, you just follow all possible paths along the
graph. So if you update B, you know you also need to update E and F. When
you update A, you know you need to update the whole graph.

The reason the graph needs to be acyclic is to avoid infinite update
looks. Let's say you had the following cyclic graph:

A<-->B

And you wanted to update A. This would trigger an update in B, which would
then trigger an update in A, and so on back and forth forever.

An easy way to implement this is to have each node (or table) keep a list
of all of the other nodes it needs to notify when it gets updated. So A
would keep B, C and D in its list. B would keep E and F in its list, and
so on.

Right now I'm experimenting with a loop that I wouldn't actually label
as
recursive but is close. It starts with a table, makes that table the
first
node in the list, then the loop starts. It gets the children of that
table
and makes a list with them as nodes and that new sublist becomes the
next
node in the main list. Then it looks at all the grandchild tables and
makes another sublist of them and that becomes the 3rd node on the main
list. I end up with a main list and each node is a sublist. The first
sublist is only 1 item long, containing the initial table. The 2nd
node/sublist is all the children, the 3rd node/sublist is the
grandchildren
and so on.

I looked into it several ways since I don't like writing a loop to
gather
data, then another to go through that same data, but found if I tried
one
loop to process, there were times I'd have to step back one level, so I
decided to list it all. The only actual recursion at this point is
getting
a list of tables from one table, then doing the same from each table in
the
list.

What you've written is essentially what I described as being a
breadth-first traversal using a queue (except you need not make these
sublists). I think generally, it would not be considered a form of
recursion. I think (but am not sure) that the technical definition of
recursion requires a method to call itself either directly or indirectly.

To clarify a potential confusion: when you're using this breadth-first
traversal algorithm you need to be working with the tree data structure,
and not the acyclic directed graph data structure.

Recall that the tree was:

A
|
+-+-+
B C D
| |
E F

with A as the root, B, C, D as its children, and E the child of B, F the
child of C.

If you wanted to update A, for example, you'd add A to the queue. Now,
you take the first element out of the queue (which is "A", leaving the
queue now empty), and then you do whatever updates you need to do on "A",
and then add all of its children in the queue (B, C and D). If the queue
is empty, you're done. But it's not empty, so you repeat: Take the first
element out of the queue (which is "B", leaving the queue as {C,D}),
update it, and add all of B's children to the queue (the queue is now
{C,D,E}). You keep repeating this until the queue is completely empty,
which should result in your processing each node exactly once.

The drawback of this algorithm is that you must always process the
entire tree. That is, you cannot, for example, only update B and its
dependents, because adding B to the queue will eventually trigger the
processing of E, but you'll miss the processing of F.

Having the dependency list as an acyclic graph allows you to only
process the parts of the trees that need to be processed.

- Oliver

 

[Hal Vaughan]

have a look at javax.swing.tree.DefaultTreeModel.

I have not looked closely, but it may be suitable for non-GUI use too.

That was one thing I considered, but was hoping to find one already
existing. With my limited experience, I'm surprised to find that there are
data types I know about that aren't easily implemented in Java.
DefaultTreeModel was close, but I could not get all the nodes in one level
easily.

Thanks for the idea!

Hal