Create tree structure in Java using PHP script

Question

I have a js application using tree structures where children of a node are stored in it's children property as an array. Data is read from a MySQL DB and the tree structure is built in a php backend. Then everything is sent as a JSON:

[
    {
        id: 1,
        children: [
            {
                id: 11
            },
            {
                id: 12
            }
        ]
    },
    {
        id: 2
    },
    {
        id: 3
    }
]

This is the PHP script that I'm using. It can be divided into 4 phases :

first I create an associative array of nodes by their id's
then I create another array taking only nodes on the first level (without parentId defined)
next I recursively iterate through the first array checking id's and parentId's and build my tree
finally I rewrite the output associative array to an indexed array

This is the whole source :

q = 'SELECT * FROM tasks';
$r = mysql_query($q);
$tasks = array();

//1.
while ($e = mysql_fetch_assoc($r)){
    $tasks[$e['Id']] = $e;
}

$sortedArray = array();

//2. get first level with no parent
foreach($tasks as $k => $v){
    if($v['parentId'] == 'null'){
        $sortedArray[$k] = $v;
        unset($tasks[$k]);
    }
}

//3. calls findChildren for first level nodes
function getChildren(array & $a1, array & $a2){
    foreach($a1 as $k => $v){
        findChildren($v, $a2, $k);      
    }
}

//recursive method checking if record's parent is already in the `sortedArray`.
//if yes, it's added to parent's `children` array. Otherwise it tries to
//find the parent in the node`s `children` array
function findChildren($rec1, array & $a2, $key){

    foreach($a2 as $k => $v){
        if($rec1['parentId'] == $v['Id']){
            $a2[$k]['children'][$rec1['Id']] = $rec1;
            unset($tasks[$key]);
        } else {
            if (isset($v['children'])){
                findChildren($rec1, $a2[$k]['children'], $key);
            }
        }
    }
}

//4. after `findChildren` `sortedArray` is an associative array, which
//is not valid for JSON
function makeIndexed(array & $arr, array & $par = null){
    if(is_null($par)){
        $arr = array_values($arr);
    } else {
        $par['children'] = array_values($arr);
    }

    for($i=0; $i<count($arr); $i++) {   
        $temp = @$arr[$i]['children'];
        if(isset($temp)) {
            makeIndexed($arr[$i]['children'], $arr[$i]);
        }       
    }
}

getChildren($tasks, $sortedArray);

makeIndexed($sortedArray);

echo json_encode($sortedArray);

Now my goal is to recreate this behaviour in a Java backend. Right now I'm just getting a flat List structure with all my events from a Hibernate query :

public static Map<String,Object> getEvents() {

    DetachedCriteria criteria = DetachedCriteria.forClass(Event.class);

    return mapOk(hibernateTemplate.findByCriteria(criteria));
}

public static Map<String,Object> mapOK(List<Event> events){

    Map<String,Object> modelMap = new HashMap<String,Object>(2);
    modelMap.put("data", events);
    modelMap.put("success", true);

    return modelMap;
}

How to tackle this ? It's been some time since I was last using Java, and I've never used it for web programming so I'm not really sure where to start and what approach should I take. Maybe this can be somehow automated ?

The PHP code is needlessly complex. The flat list can be transposed into the tree array with a single `foreach` and a single reference. For example see: [How can I convert a series of parent-child relationships into a hierarchical tree?](http://stackoverflow.com/questions/2915748/how-can-i-convert-a-series-of-parent-child-relationships-into-a-hierarchical-tre/8285070#8285070) - This might also be the most straight forward approach for Java, but I'm not fluent with Java. — hakre, Dec 17 '12 at 01:17
I'm neither fluent with java nor php as I'm a fronted developer and always worked with python/django backends so indeed it may be overcomplexed. But at least it works :) — mike_hornbeck, Dec 17 '12 at 01:29

score 1 · Accepted Answer · answered Dec 19 '12 at 01:17

Not sure why somebody -1'ed my question, but here's what I came up with :

import java.io.IOException;
import java.util.HashMap;
import java.util.Iterator;
import java.util.List;
import java.util.Map;

import org.springframework.stereotype.Component;
import org.codehaus.jackson.JsonGenerationException;
import org.codehaus.jackson.map.JsonMappingException;
import org.codehaus.jackson.map.ObjectMapper;
import org.json.*;

import org.com.model.Task;

@Component
public class ReturnTasks {

    private static JSONObject sortedByParentTasks = null;
    private static JSONArray tasksTree = null;
    private static JSONObject taskChildrenObject;

    /**
     * Generates JSON String to return in the modelAndView
     * @param events
     * @return
     * @throws JSONException 
     * @throws IOException 
     * @throws JsonMappingException 
     * @throws JsonGenerationException 
     */

    public static String mapOK(List<Task> events) throws JSONException, JsonGenerationException, JsonMappingException, IOException{
        tasksTree = null;
        tasksTree = new JSONArray();
        sortedByParentTasks = null;
        sortedByParentTasks = new JSONObject();
        tasksTree = makeTree(events);

        return tasksTree.toString();
    }

    private static JSONArray makeTree(List<Task> list) throws JSONException, JsonGenerationException, JsonMappingException, IOException{

        Iterator<Task> listIterator = list.iterator();
        String parentId;

        while(listIterator.hasNext()){
            Task task = listIterator.next();
            JSONArray equalParentId;
            parentId = ""+task.getParentId();
            String json = new ObjectMapper().writeValueAsString(task);
            JSONObject taskJSON = new JSONObject(json);

            if (sortedByParentTasks.has(parentId)){
                sortedByParentTasks.accumulate(parentId, taskJSON);
            } else {
                equalParentId = new JSONArray();
                equalParentId.put(taskJSON);
                sortedByParentTasks.put(parentId, equalParentId);
            }
        }

        addNodes(sortedByParentTasks.getJSONArray("null"));

        return tasksTree;
    }

    private static void addNodes(JSONArray nodes) throws JSONException{
        for(int i=0, l=nodes.length(); i<l; i++){
            taskChildrenObject = nodes.getJSONObject(i);
            listHierarchy(taskChildrenObject);
            tasksTree.put(taskChildrenObject);
        }
    }

    private static void listHierarchy(JSONObject task) throws JSONException{
        JSONArray childrenArray = new JSONArray();
        JSONArray childNodes = new JSONArray();

        try {
            childNodes = sortedByParentTasks.getJSONArray(""+task.get("Id"));
        }catch(JSONException e){} 

        if (childNodes.length() > 0){
            for (int i=0, l=childNodes.length(); i<l; i++) {
                JSONObject childObject = childNodes.getJSONObject(i);
                childrenArray.put(childObject);
                try{
                    task.put("children", childrenArray);
                    task.put("leaf", false);
                }catch(JSONException e){}

                listHierarchy(childObject);
            }           
        }
    }

    /**
     * Generates modelMap to return in the modelAndView in case
     * of exception
     * @param msg message
     * @return
     */
    public static String mapError(String msg){

        Map<String,Object> modelMap = new HashMap<String,Object>(2);
        modelMap.put("message", msg);
        modelMap.put("success", false);

        return modelMap.toString();
    } 
}

Create tree structure in Java using PHP script

1 Answers1