• Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other Pie Elite all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Jeanne Boyarsky
  • Ron McLeod
  • Paul Clapham
  • Liutauras Vilda
Sheriffs:
  • paul wheaton
  • Rob Spoor
  • Devaka Cooray
Saloon Keepers:
  • Stephan van Hulst
  • Tim Holloway
  • Carey Brown
  • Frits Walraven
  • Tim Moores
Bartenders:
  • Mikalai Zaikin

creating tree structure from flat database and parsing it into JSON (Spring)

 
Ranch Hand
Posts: 39
IntelliJ IDE MySQL Database Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
So here I'm once again...
I've got this data model saved in my in memory database H2:



Examples of objects in repository:  

And this database contains almost 10 k records like that.  
I need to get all this data out, create tree from them (i literally have got no idea how-after few guides-still empty) and send it to frontend in one JSON.  
Desired JSON example:

It looks like this JSON answer is an array (Im not sure about it)
Any idea how to start? How should it look like step by step? I am sitting and unfortunately I cannot get to it. I am looking for a simple and clear solution. I will work on performance after I make the first working version (if I can do it at all).
Main problem for me that I have got X roots- I've got no idea how to make tree that have got many entry points
Thanks in advance for any help!
 
Saloon Keeper
Posts: 15510
363
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
First take all of the entries out of the database and make them into tree nodes and stick them into a map keyed by node ID.

Then for each node in the map, if it's not a root node, add it to the children of its parent node, and remove it from the map.

Finally the remaining node in the map is the root of the tree, and you can serialize the whole tree just by serializing the root.
 
Jan Kaczmarek
Ranch Hand
Posts: 39
IntelliJ IDE MySQL Database Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
I inspected whole documentation and I saw that Im forced to use 2 types of objects :

and


Does it change a lot?
It seems to me the way to solve this:
1) I am creating a POJO that will look like Organization
String id;
String name;
String parentId;
and save them in HashMap <String [id], Organization>
2) Creates an OrganizationTree object and initializes an empty array in it with a length equal to the number of objects marked as "root"
2) I drop all root objects into OrganizationTree (previously changed their type to OrganizationSubtree) and remove them from the map.
3) I iterate around the map taking the first objects that point to root as the parent object from the map and removing them from the map and putting them in the parent table.
4) I iterate across the map like this until it's empty.
It seems to me the simplest, but also terrible in terms of efficiency. Every time I will have to search every object and every array in it and in every array - another object with arrays (it is not known how many layers, there can be hundreds) + every time i add another children I need to create new array and copy the old one - because at the beginning i dont know how many childrens may parent have
 
Stephan van Hulst
Saloon Keeper
Posts: 15510
363
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Sorry, I might have put you on the wrong track by suggestion you remove nodes from the map.

You only need to iterate over all organizations twice:

Anyway, I don't see the point of the OrganizationTree class. At the end of the algorithm above, the root variable will hold the root of the entire tree and if you use a library such as JSON-B, you can easily serialize the whole thing to JSON in one go.

By the way, I just saw that your Organization class already has a subOrgs field, so it already IS a tree.
 
Jan Kaczmarek
Ranch Hand
Posts: 39
IntelliJ IDE MySQL Database Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Unfortunately - I have to use OranizationSubtree and OrganizationTree, I have these two in the requirements and I can't change it, so I have to adapt your solution somehow. Version with entity "Organization" is completely eliminated.
It seems to me a big problem that the way to store data is an array. By adding another node I will have to copy the array each time and create a new one, larger by one
 
Stephan van Hulst
Saloon Keeper
Posts: 15510
363
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Just use a List instead of an array.
 
Jan Kaczmarek
Ranch Hand
Posts: 39
IntelliJ IDE MySQL Database Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
So after few hours of tests, coding and thinking "i hate data tree structures" I created something like this:





So I decided to use Org model anyway.
Eveything should work but hm... Its not looking for childrens and I have got no idea why
 
Jan Kaczmarek
Ranch Hand
Posts: 39
IntelliJ IDE MySQL Database Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Another change : Now it returns only last children's of one root, thats all
 
Jan Kaczmarek
Ranch Hand
Posts: 39
IntelliJ IDE MySQL Database Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Debugging result. Here is a problem, but I have got no idea how to fix it.
wynik.jpg
[Thumbnail for wynik.jpg]
 
Jan Kaczmarek
Ranch Hand
Posts: 39
IntelliJ IDE MySQL Database Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
For the ancestors! I love my life FIXED! Now just optimization.
I was overwriting the root all the time. In addition, the process of searching for descendants was not assigned to anything. It was searching for searching.

 
reply
    Bookmark Topic Watch Topic
  • New Topic