Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > comp.lang.java.programmer > #33315 > unrolled thread
| Started by | mike <mikaelpetterson@hotmail.com> |
|---|---|
| First post | 2015-12-08 10:29 -0800 |
| Last post | 2016-01-08 12:13 +0000 |
| Articles | 6 — 3 participants |
Back to article view | Back to comp.lang.java.programmer
searching a tree of objects mike <mikaelpetterson@hotmail.com> - 2015-12-08 10:29 -0800
Re: searching a tree of objects Eric Douglas <e.d.programmer@gmail.com> - 2015-12-08 10:43 -0800
Re: searching a tree of objects Martin Gregorie <martin@address-in-sig.invalid> - 2015-12-08 19:22 +0000
Re: searching a tree of objects mike <mikaelpetterson@hotmail.com> - 2016-01-07 21:59 -0800
Re: searching a tree of objects Eric Douglas <e.d.programmer@gmail.com> - 2016-01-08 13:35 -0800
Re: searching a tree of objects Martin Gregorie <martin@address-in-sig.invalid> - 2016-01-08 12:13 +0000
| From | mike <mikaelpetterson@hotmail.com> |
|---|---|
| Date | 2015-12-08 10:29 -0800 |
| Subject | searching a tree of objects |
| Message-ID | <a8beac79-4ac8-4abd-b680-ab4a3112dd51@googlegroups.com> |
Hi,
We have a tree of objects with root at the top.
Now I want to search the tree for a specific node (object)
search string will look like:
name=<index>,name2=<index2>,name3=<index3>
example could be:
RootType=1,Device=1,DdcDevice=1
Rootype=1
|
-----------
| |
Device=1 Equipment=1
|
---------------------------------------
| | | |
DbcDevice=1 DbcDevice=2 DrpDevice=2 VrpDevice=1
In each object I have the information name=<index> in an attribute called identifier.
How can I use the search string and find the correct node that is DbcDevice=1 and return another attribute for this object.
//mike
[toc] | [next] | [standalone]
| From | Eric Douglas <e.d.programmer@gmail.com> |
|---|---|
| Date | 2015-12-08 10:43 -0800 |
| Message-ID | <278bc9fa-34a7-4b93-ba49-1d12711fb354@googlegroups.com> |
| In reply to | #33315 |
On Tuesday, December 8, 2015 at 1:29:46 PM UTC-5, mike wrote: > Hi, > > We have a tree of objects with root at the top. > Now I want to search the tree for a specific node (object) > search string will look like: > > name=<index>,name2=<index2>,name3=<index3> > > example could be: > > RootType=1,Device=1,DdcDevice=1 > > Rootype=1 > | > ----------- > | | > Device=1 Equipment=1 > | > --------------------------------------- > | | | | > DbcDevice=1 DbcDevice=2 DrpDevice=2 VrpDevice=1 > > In each object I have the information name=<index> in an attribute called identifier. > > How can I use the search string and find the correct node that is DbcDevice=1 and return another attribute for this object. > > //mike We have your tree but do you have an object? Do you have sample code you're already trying to work with, or are you asking in general how you could create new custom classes to do this method?
[toc] | [prev] | [next] | [standalone]
| From | Martin Gregorie <martin@address-in-sig.invalid> |
|---|---|
| Date | 2015-12-08 19:22 +0000 |
| Message-ID | <n47ala$asp$1@dont-email.me> |
| In reply to | #33315 |
On Tue, 08 Dec 2015 10:29:24 -0800, mike wrote: > Hi, > > We have a tree of objects with root at the top. > Now I want to search the tree for a specific node (object) > search string will look like: > > name=<index>,name2=<index2>,name3=<index3> > > example could be: > > RootType=1,Device=1,DdcDevice=1 > > Rootype=1 > | > ----------- | | > Device=1 Equipment=1 > | > --------------------------------------- > | | | | > DbcDevice=1 DbcDevice=2 DrpDevice=2 VrpDevice=1 > > In each object I have the information name=<index> in an attribute > called identifier. > > How can I use the search string and find the correct node that is > DbcDevice=1 and return another attribute for this object. > What is the purpose of your tree and what do you expect to return from searching it? If you expect to return a path to the target node, e.g "RootType,Device.RrpDevice" as well as and attribute of the target node content, then simply recursively walking the tree is your best bet. OTOH, If all you want to do is directly access a node or the subtree beneath it, use a HashMap as a fast node index. Use a TreeMap if you need an ordered index of node names. -- martin@ | Martin Gregorie gregorie. | Essex, UK org |
[toc] | [prev] | [next] | [standalone]
| From | mike <mikaelpetterson@hotmail.com> |
|---|---|
| Date | 2016-01-07 21:59 -0800 |
| Message-ID | <531d0446-8946-428b-a239-981db96a1bda@googlegroups.com> |
| In reply to | #33315 |
I will make some simplifications and clarifications:
I have two java lists containing names ( parents and chilren). So when I have Equipment in childlist the same index in parent list will be Rootype.
Given is a "path" describing the way to a "leaf". See below.
{RootType,DfcDdd,DbcDevice,Nhost}
This what I want to search for using above mentioned list.
Rootype
|
----------------------------------------------------------
| | |
Device Equipment DfcDdd
| | |
----------------------- --------------------
| | | |
DbcDevice DrpDevice DbcDevice DrpDevice
| |
Nhost Nhost
But as you can see in the tree structure we have two paths and only one is correct.The other one contains the Device in path so the Nhost under there is not correct.
My approach has been to go bottom-up.
I check the child list for all the 'Nhost' name and get the indexes for each (2 in my simplified case).
I the first index and check the parent list and I get the matching DbcDevice. I need to check that vs the "wanted" path and it matches. Then when I reach Device and compare with my seacrch I see this is wrong path.....
As you can see it gets very complicated
Is there any algorithm for this? Or simply put a better way to do it.
//mikael
[toc] | [prev] | [next] | [standalone]
| From | Eric Douglas <e.d.programmer@gmail.com> |
|---|---|
| Date | 2016-01-08 13:35 -0800 |
| Message-ID | <2021b312-275d-442a-ae74-c31902e82bb9@googlegroups.com> |
| In reply to | #33450 |
On Friday, January 8, 2016 at 12:59:31 AM UTC-5, mike wrote:
> I will make some simplifications and clarifications:
>
>
> I have two java lists containing names ( parents and chilren). So when I have Equipment in childlist the same index in parent list will be Rootype.
>
> Given is a "path" describing the way to a "leaf". See below.
>
> {RootType,DfcDdd,DbcDevice,Nhost}
>
> This what I want to search for using above mentioned list.
>
> Rootype
> |
> ----------------------------------------------------------
> | | |
> Device Equipment DfcDdd
> | | |
> ----------------------- --------------------
> | | | |
> DbcDevice DrpDevice DbcDevice DrpDevice
> | |
> Nhost Nhost
>
>
>
>
> But as you can see in the tree structure we have two paths and only one is correct.The other one contains the Device in path so the Nhost under there is not correct.
>
> My approach has been to go bottom-up.
>
> I check the child list for all the 'Nhost' name and get the indexes for each (2 in my simplified case).
>
> I the first index and check the parent list and I get the matching DbcDevice. I need to check that vs the "wanted" path and it matches. Then when I reach Device and compare with my seacrch I see this is wrong path.....
> As you can see it gets very complicated
>
> Is there any algorithm for this? Or simply put a better way to do it.
>
> //mikael
Again this is very vague, showing a tree model with no actual code. How are you searching? What are you searching? What exactly is the problem? Do you have some sample code to fix? Are you using array classes, custom objects, or JTree? What's your model look like?
Normally a search is top-down. If you say you want a JTree node called {RootType,DfcDdd,DbcDevice,Nhost} , it checks for a root node called RootType, then checks it's children for a DfcDdd, etc until it hits Nhost or a missing branch. If you do a search all for Nhost you should get 2 results, a {RootType,DfcDdd,DbcDevice,Nhost} and a {RootType,Device,DbcDevice,Nhost} .
[toc] | [prev] | [next] | [standalone]
| From | Martin Gregorie <martin@address-in-sig.invalid> |
|---|---|
| Date | 2016-01-08 12:13 +0000 |
| Message-ID | <n6o961$8iq$1@dont-email.me> |
| In reply to | #33450 |
On Thu, 07 Jan 2016 21:59:14 -0800, mike wrote:
> I will make some simplifications and clarifications:
>
>
> I have two java lists containing names ( parents and chilren). So when I
> have Equipment in childlist the same index in parent list will be
> Rootype.
>
> Given is a "path" describing the way to a "leaf". See below.
>
> {RootType,DfcDdd,DbcDevice,Nhost}
>
> This what I want to search for using above mentioned list.
>
> Rootype
> |
>
----------------------------------------------------------
> | | |
> Device Equipment DfcDdd
>
| | |
> -----------------------
--------------------
> | |
| |
> DbcDevice DrpDevice DbcDevice
DrpDevice
> | |
> Nhost Nhost
>
>
>
>
> But as you can see in the tree structure we have two paths and only one
> is correct.The other one contains the Device in path so the Nhost under
> there is not correct.
>
> My approach has been to go bottom-up.
>
> I check the child list for all the 'Nhost' name and get the indexes for
> each (2 in my simplified case).
>
> I the first index and check the parent list and I get the matching
> DbcDevice. I need to check that vs the "wanted" path and it matches.
> Then when I reach Device and compare with my seacrch I see this is wrong
> path.....
> As you can see it gets very complicated
>
> Is there any algorithm for this? Or simply put a better way to do it.
>
Being fundamentally a database guy, I'd start from a fully normalised[1]
entity-relationship diagram like this:
---------
( RootType)
---------
|
/|\
----------
( Category )
----------
|
/|\
------------
( DeviceType )
------------
|
/|\
-------
( Device)
-------
Where each crows-foot represents a 1:m relationship and each entity has a
unique key (name). This structure directly supports your 'path' method of
naming devices and, because the keys are unique, that eliminates your
duplicate name problem by definition.
Of course, if all entities above the Item contain no information apart
from the name, you might choose to collapse the structure into a single
entity with a compound key made up from the four name fields, e.g.
rootName,categoryName,deviceType,deviceName, in which case you could
implement the entity as a single class and use either a TreeMap or a
HashMap to access instances of it. Which Map type you'd choose would
depend on whether you need to produce lists or not.
If there is additional data to be stored in each entity, there are
several ways of implementing this structure. Which one to use depends on
the number of instances of each entity and the data they contain. Off the
top of my head:
1)use a database such as PostgreSQL, MariaDB, Derby or H2. These are
all FOSS and the latter two are pure Java implementations.
In this case you'd use the key hierarchy to show relationships,
i.e. Category's prime key would be rootName,categoryName where
rootName is a foreign key mapped to the RootType's prime key
and Category would be indexed on its prime key.
2)implement each entity as a class and use a TreeMap or HashMap to
enforce prime key uniqueness, i.e this is effectively an
in-memory database.
3)as for 2, but make each class carry a reference to its parent
and add an ArrayList or Map to each parent that contains references to
its children. This lets you traverse the entire structure in either
direction by following references.
4)....
Which way you go depends on how you intend to use the data, what data
each entity contains and the size of each entity population - and
currently only you know these details.
[1] 'fully normalised' means 3rd normal form, where every attribute
depends on a single key, i.e. there are no repeated attributes in any
entity.
--
martin@ | Martin Gregorie
gregorie. | Essex, UK
org |
[toc] | [prev] | [standalone]
Back to top | Article view | comp.lang.java.programmer
csiph-web