Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.java.programmer > #10286 > unrolled thread

Collection to implement linked structure traverse up and down

Back to article view | Back to comp.lang.java.programmer

Contents

  Collection to implement linked structure traverse up and down ruds <rudranee@gmail.com> - 2011-11-27 23:53 -0800
    Re: Collection to implement linked structure traverse up and down Arved Sandstrom <asandstrom3minus1@eastlink.ca> - 2011-11-28 07:32 -0400
      Re: Collection to implement linked structure traverse up and down Wayne <nospam@all.invalid> - 2011-12-01 10:39 -0500
        Re: Collection to implement linked structure traverse up and down ruds <rudranee@gmail.com> - 2011-12-04 23:57 -0800
          Re: Collection to implement linked structure traverse up and down Lew <lewbloch@gmail.com> - 2011-12-05 15:08 -0800
            Re: Collection to implement linked structure traverse up and down ruds <rudranee@gmail.com> - 2011-12-05 21:55 -0800
    Re: Collection to implement linked structure traverse up and down Roedy Green <see_website@mindprod.com.invalid> - 2011-11-29 17:01 -0800
      Re: Collection to implement linked structure traverse up and down Henk van Voorthuijsen <voorth@xs4all.nl> - 2011-12-05 02:41 -0800
    Re: Collection to implement linked structure traverse up and down Martin Gregorie <martin@address-in-sig.invalid> - 2011-11-30 21:17 +0000

#10286 — Collection to implement linked structure traverse up and down

Hi,
I want to implement a tree or a linked structure where I can traverse
to the parent of a node also and the same node refers to another data
related to it too.
for example i have a set [0,1,2,3,...10], consider these as levels,
so ) will be at top i.e the root, 1 will be first level, and so on.
each of these levels will again have some branches and some data needs
to be referenced with this too for comparison with another similar
tree of this kind. Also, once I get the comparion of the branch X done
I need to traverse to its parent level and it higher level.
I think TreeMapClass and LinkedHashMapClass will be helpfull to me in
this regard.
This need not be a tree, it can be a linked list too.
Please tell me am i on the right path? Kindly, suggest the
implementation too.

[toc] | [next] | [standalone]

#10290

On 11-11-28 03:53 AM, ruds wrote:
> Hi,
> I want to implement a tree or a linked structure where I can traverse
> to the parent of a node also and the same node refers to another data
> related to it too.
> for example i have a set [0,1,2,3,...10], consider these as levels,
> so ) will be at top i.e the root, 1 will be first level, and so on.
> each of these levels will again have some branches and some data needs
> to be referenced with this too for comparison with another similar
> tree of this kind. Also, once I get the comparion of the branch X done
> I need to traverse to its parent level and it higher level.
> I think TreeMapClass and LinkedHashMapClass will be helpfull to me in
> this regard.
> This need not be a tree, it can be a linked list too.
> Please tell me am i on the right path? Kindly, suggest the
> implementation too.

If I understand you correctly, one of your requirements is that each
node of the data structure has associated user data, which is distinct
from references to other nodes. This is common.

The distinguishing feature of a node for a singly linked list is that it
has a reference to a "next" sibling. Nodes for doubly linked lists have
two references, one to a "previous" sibling, one to a "next" sibling.
Nodes for a binary tree have zero, one or two references, where any
reference is to a "child". Any or all of these nodes can be implemented
with objects that have not only the required references but also
variable, user-defined data.

It's also helpful to distinguish between concept and implementation. At
this stage we're talking concepts, and the language is clearly that of
trees. In particular where you are talking about tree comparisons this
is all very standard stuff...although your determination of how two
trees compare will typically not start at the bottom.

I don't think TreeMap or LinkedHashMap will help you much. These are
both maps. You can distort them into trees but that's not their intended
purpose. If you're looking to locate a starting implementation you could
do worse than use javax.swing.tree.TreeModel (implementation class
javax.swing.tree.DefaultTreeModel) and javax.swing.tree.TreeNode
(MutableTreeNode, DefaultMutableTreeNode). These are general purpose and
don't have to be used with Swing at all.

AHS

[toc] | [prev] | [next] | [standalone]

#10402

On 11/28/2011 6:32 AM, Arved Sandstrom wrote:
> On 11-11-28 03:53 AM, ruds wrote:
>> Hi,
>> I want to implement a tree or a linked structure where I can traverse
>> to the parent of a node also and the same node refers to another data
>> related to it too.
>> for example i have a set [0,1,2,3,...10], consider these as levels,
>> so ) will be at top i.e the root, 1 will be first level, and so on.
>> each of these levels will again have some branches and some data needs
>> to be referenced with this too for comparison with another similar
>> tree of this kind. Also, once I get the comparion of the branch X done
>> I need to traverse to its parent level and it higher level.
>> I think TreeMapClass and LinkedHashMapClass will be helpfull to me in
>> this regard.
>> This need not be a tree, it can be a linked list too.
>> Please tell me am i on the right path? Kindly, suggest the
>> implementation too.
> 
> If I understand you correctly, one of your requirements is that each
> node of the data structure has associated user data, which is distinct
> from references to other nodes. This is common.
> 
> The distinguishing feature of a node for a singly linked list is that it
> has a reference to a "next" sibling. Nodes for doubly linked lists have
> two references, one to a "previous" sibling, one to a "next" sibling.
> Nodes for a binary tree have zero, one or two references, where any
> reference is to a "child". Any or all of these nodes can be implemented
> with objects that have not only the required references but also
> variable, user-defined data.
> 
> It's also helpful to distinguish between concept and implementation. At
> this stage we're talking concepts, and the language is clearly that of
> trees. In particular where you are talking about tree comparisons this
> is all very standard stuff...although your determination of how two
> trees compare will typically not start at the bottom.
> 
> I don't think TreeMap or LinkedHashMap will help you much. These are
> both maps. You can distort them into trees but that's not their intended
> purpose. If you're looking to locate a starting implementation you could
> do worse than use javax.swing.tree.TreeModel (implementation class
> javax.swing.tree.DefaultTreeModel) and javax.swing.tree.TreeNode
> (MutableTreeNode, DefaultMutableTreeNode). These are general purpose and
> don't have to be used with Swing at all.
> 
> AHS

In addition to javax.swing.tree.*, take a look at the org.w3c.dom.Node.

-- 
Wayne

[toc] | [prev] | [next] | [standalone]

#10518

Thanks all.
Roedy Green: Can you elaborate some more on "a HashMap an ArrayList
and a TreeSet simultaneously all on the same group of objects."

[toc] | [prev] | [next] | [standalone]

#10536

ruds wrote:
> Roedy Green: Can you elaborate some more on "a HashMap an ArrayList
> and a TreeSet simultaneously all on the same group of objects."

Consider this fragment:

 Map<Foo, Bar> bars = new HashMap<>();
 List<Bar> barVals = new ArrayList<>();
 Set<Foo> foos = new TreeSet<>();
...
 Foo foo = new Foo();
 Bar bar = new Bar();
 bars.put(foo, bar);
 barVals.add(bar);
 foos.add(foo);
...

A pointer to the same 'foo' appears in 'bars' and in 'foos'.  A pointer to the same 'bar' appears in 'bars' and in 'barVals'.

Do that again with a new 'foo' and a new 'bar' a few times and you have "a group of objects" in all three collections simultaneously.

-- 
Lew

[toc] | [prev] | [next] | [standalone]

#10546

On Dec 6, 4:08 am, Lew <lewbl...@gmail.com> wrote:
> ruds wrote:
> > Roedy Green: Can you elaborate some more on "a HashMap an ArrayList
> > and a TreeSet simultaneously all on the same group of objects."
>
> Consider this fragment:
>
>  Map<Foo, Bar> bars = new HashMap<>();
>  List<Bar> barVals = new ArrayList<>();
>  Set<Foo> foos = new TreeSet<>();
> ...
>  Foo foo = new Foo();
>  Bar bar = new Bar();
>  bars.put(foo, bar);
>  barVals.add(bar);
>  foos.add(foo);
> ...
>
> A pointer to the same 'foo' appears in 'bars' and in 'foos'.  A pointer to the same 'bar' appears in 'bars' and in 'barVals'.
>
> Do that again with a new 'foo' and a new 'bar' a few times and you have "a group of objects" in all three collections simultaneously.
>
> --
> Lew

thanks will check this out.

[toc] | [prev] | [next] | [standalone]

#10344

On Sun, 27 Nov 2011 23:53:30 -0800 (PST), ruds <rudranee@gmail.com>
wrote, quoted or indirectly quoted someone who said :

>Please tell me am i on the right path? 

There are two kinds of links:

1. links which define which objects are in the Set and how to find
them.

2. links that define interrelationships between the objects.

I would expect things to become clearer if you expected of your
Collection to handle type (1), and you handled type (2) yourself
independent of the Collection.

I might help to recall it is possible to have a HashMap an ArrayList
and a TreeSet simultaneously all on the same group of objects.

So in your case you can have a Map for finding things, and a
completely independent set of links defining your directed graph (to
use the mathematical name for such a generic structure).

If it is truly a tree, don't forget about JTree.

see http://mindprod.com/jgloss/treeset.html
http://mindprod.com/jgloss/treemap.html
http://mindprod.com/jgloss/jtree.html
http://mindprod.com/jgloss/tree.html

-- 
Roedy Green Canadian Mind Products
http://mindprod.com
For me, the appeal of computer programming is that
even though I am quite a klutz,
I can still produce something, in a sense
perfect, because the computer gives me as many
chances as I please to get it right.
 

[toc] | [prev] | [next] | [standalone]

#10521

>
> If it is truly a tree, don't forget about JTree.
>

You mean TreeModel and its implementation(s), I hope?

Henk

[toc] | [prev] | [next] | [standalone]

#10378

On Sun, 27 Nov 2011 23:53:30 -0800, ruds wrote:

> Hi,
> I want to implement a tree or a linked structure where I can traverse to
> the parent of a node also and the same node refers to another data
> related to it too.
> for example i have a set [0,1,2,3,...10], consider these as levels, so )
> will be at top i.e the root, 1 will be first level, and so on. each of
> these levels will again have some branches and some data needs to be
> referenced with this too for comparison with another similar tree of
> this kind. Also, once I get the comparion of the branch X done I need to
> traverse to its parent level and it higher level.
> I think TreeMapClass and LinkedHashMapClass will be helpfull to me in
> this regard.
> This need not be a tree, it can be a linked list too.
> Please tell me am i on the right path? Kindly, suggest the
> implementation too.
>
The main problem is that, unless I missed something, none of the standard 
Tree* classes implement a getParent() method - if you need that operation 
you'll probably need to implement a red-black tree or Btree yourself, but 
once that's done there's no reason why each node shouldn't use some 
Collection class to hold your data items.


-- 
martin@   | Martin Gregorie
gregorie. | Essex, UK
org       |

[toc] | [prev] | [standalone]

Back to top | Article view | comp.lang.java.programmer

csiph-web