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

Groups > comp.lang.java.programmer > #33455

Re: searching a tree of objects

Show all headers | View raw

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       |

Back to comp.lang.java.programmer | Previous | Next — Previous in thread | Find similar | Unroll thread

Thread

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

csiph-web