Make a Tree from List of Array (ResultSet for example)

Question

I have a List of Arrays, like this one:

List<String[]> myList = new ArrayList<String[]>();
myList.add( new String[]{"A1","B1","C1","D1","values"} );
myList.add( new String[]{"A1","B1","C2","D1","values"} );
myList.add( new String[]{"A1","B1","C2","D2","values"} );
myList.add( new String[]{"A2","B1","C1","D1","values"} );
myList.add( new String[]{"A2","B1","C1","D2","values"} );

I need fill An Object that have dependences with the fathers, so:

• A1 have only one child, B1.
  • B1 have 2 children, C1 and C2.
    • C1 have 1 child, D1, that have the values...
    • C2 have 2 children, D1 and D2, that have the values...
• A2 have only one child, B1 (Not the same that the other one)
  • B1 have only one child, C1... etc.

---

What kind of structure do you think is better? I need the names A1, B1, etc.

I have probe with Maps, Arrays, Lists... I think that the algorithm is not possible... :( :(

Please, HELP!

Edit explaining:

I have a ResultSet from a DataBase that have 5 or 6 GROUP BY clauses. I have all the plain data and

I need to make an structure with Text Objects, for example:

Person A - Building 1 - Tower 1 - Some Text A

Person A - Building 1 - Tower 2 - Another Text

Person A - Building 2 - Tower 1 - Another one Text

Person A - Building 2 - Tower 3 - My Text

Person B - Building 1 - Tower 2 - Any Text

Person B - Building 3 - Tower 1 - A Text...

I need an Object structure for this data... Is it possible?

Solution 1

I DID IT ! OH MY GOD! :D :D :D :D :D :D :D...

private static void finalFillerTotalSuperSpecial(List<String[]> initialList, HashMap<String,Object> mapa){

     String[] currentElement = null;
     String currentKey = null;

     String[] nextElement = null;
     String nextKey = null;
     int i=0,start,end;

     while (i < initialList.size()) {
     start = i;

     currentElement = initialList.get( i++ );
     currentKey = currentElement[0];

     if (i<initialList.size()){
         nextElement = initialList.get( i );
         nextKey = nextElement[0];
     }

     HashMap<String,Object> insideMap = new HashMap<String,Object>(); 
     mapa.put(currentKey, insideMap);

     while (currentKey.equals(nextKey) && i < initialList.size()) {
         currentElement = initialList.get( i++ );
         currentKey = currentElement[0];

         if (i<initialList.size()){
         nextElement = initialList.get( i );
         nextKey = nextElement[0];
         }

     }
     end = i;

     List<String[]> listOfCurrentElements = new ArrayList<String[]>();
     for (int j=start;j<end;j++)
         listOfCurrentElements.add( getNextArray(initialList.get(j)) );

     if ( listOfCurrentElements.get(0).length>1 )
         finalFillerTotalSuperSpecial(listOfCurrentElements,insideMap);
     else
         insideMap.put(listOfCurrentElements.get(0)[0], null);
     }



 }

Solution 2

Of course it is possible. :)

I think what you're describing can be solved by a generic or n-ary tree. That is a tree where each node can have any number of children. I wrote something that does this in Java.

If you don't want to build a tree can build use a Map<String, Set<String>>. This doesn't really give you easy access to tree operations, but it should maintain the relationships:

Map<String, Set<String>> myNodes = new LinkedHashMap<String, Set<String>>();
for(String[] myArray : myList) {
   String previousNode = null;
   for(String node : myArray) {
      if(myNodes.get(node) == null) {
         myNodes.put(node, new HashSet<String>());
      }

      if(previousNode != null) {
         myNodes.get(previousNode).add(node);
      }

      previousNode = node;
   }
}

So you essentially get (I'm using JSON to demonstrate):

{
   A1: ["B1"],
   A2: ["B1"],
   B1: ["C1", "C2"],
   C1: ["D1"],
   C2: ["D1", "D2"],
   D1: ["values"],
   D2: ["values"]
}

This is much more difficult to traverse however, than a tree.

Solution 3

So you want to build a tree structure from this list specific representation of the tree.

As for any tree structure, its nodes can have 0 to n children, so the children could trivially be stored in a List (or optionally, a Map, if you want fast name lookup). For this task, storing the parent reference doesn't seem necessary.

Then you just need to iterate through myList. For each array element,

1. Take the root of your existing tree.
2. Iterate through the array.
3. For each string in the array, check whether the current tree node has a child node with this name.
4. If not, create it and add it to the tree.
5. Move to the child node (so it becomes the current node).
6. Take the next string from the array and repeat from step 3.
7. Take the next array from the list and repeat from step 1.

Comments

[gcbenison]

Looks like you need a trie data structure. There's got to be a standard Java implementation.

[ganzux]

@Vivin Paliath I have read your implementation and it could be useful... GenericTreeNode for the element to storage... Now I am going to read to @Péter Török with the algorithm...

[ganzux]

Wow, it looks great but... the function musn´t be recursive?

[Vivin Paliath]

@ganzux You can traverse a tree iteratively or recursively. Recursively seems easier to me. An iterative traversal requires a secondary data structure (node stack).

[ganzux]

Ok, your code works BUT the children are the same... For example, with A1 I have B1 and I have the SAME B1 with A2, and although the name is the same, are different Objects... For example, if I call "D1" I get "values", but I don´t know what values are... Are from A1-B1-C1...

[Vivin Paliath]

@ganzux, I guess the problem is that it's not clear what your data is meant to represent. I tried to infer a tree-structure from what you posted in your question. What is "values" supposed to mean? Also, what do you mean that the children are the same?

[ganzux]

@Vivin Paliath Ok, I tell you all the problem (THANKS for your help): ----------- I have a ResultSet from a DataBase that have 5 or 6 GROUP BY clauses. I have all the plain data and I need to make an structure with Text Objects, for example: ----------- Person A - Building 1 - Tower 1 - Some Text A Person A - Building 1 - Tower 2 - Another Text Person A - Building 2 - Tower 1 - Another one Text Person A - Building 2 - Tower 3 - My Text Person B - Building 1 - Tower 2 - Any Text Person B - Building 3 - Tower 1 - A Text... ------------ I need an Object structure for yhis data... Is it possible?

[Vivin Paliath]

Can you add this as an edit to your original question? It's hard to read it from the comments.

[Vivin Paliath]

@ganzux From looking at your data, your best bet would be to build an actual tree.

[ganzux]

"Actual tree"? With your algorith? This is not valid... Is it?

[Vivin Paliath]

@ganzux Not with my algorithm, but by using an actual tree class.

[ganzux]

@Vivin Paliath, OK, I am going to do it now ! :)

[ganzux]

@Vivin Paliath, I have been implementing some code using your structure and, for me, I think is better to have a Map instead a List of nodes because, as you see, it can´t repeat ;)

[ganzux]

@Vivin Paliath bffffffff... I am trying to do it but it´s too difficult... Where can I post it for someone can help me? Thanks

[ganzux]

I am with the algorithm, but it´s complicated... As soon as I do something, I will advise