Construct multidimensional array from flat array

Question

Hi i am receiving a flat array from a service as follows

    [0] [] (@bf4f219)   
    [0] Object (@a55f1a9)   
        breadcrumb  "{2}"   
        entity_name "parent 2"  
        id  2   
        level   1   
        parent_id   0

    [1] Object (@a5be281)   
        breadcrumb  "{2,4}" 
        entity_name "child for parent 2"    
        id  4   
        level   2   
        parent_id   2

    [2] Object (@a5bea01)   
        breadcrumb  "{2,4,5}"   
        entity_name "child for 4"   
        id  5   
        level   3   
        parent_id   4

    [3] Object (@a5ed179)   
        breadcrumb  "{2,4,5,7}" 
        entity_name "child for 5"   
        id  7   
        level   4   
        parent_id   5

    [4] Object (@a5ed6d1)   
        breadcrumb  "{2,6}" 
        entity_name "child 2 for parent 2"  
        id  6   
        level   2   
        parent_id   2

    [5] Object (@a5edb09)   
        breadcrumb  "{2,8}" 
        entity_name "another child for 2"   
        id  8   
        level   2   
        parent_id   2

    [6] Object (@a5edda9)   
        breadcrumb  "{2,9}" 
        entity_name "another child for 2"   
        id  9   
        level   2   
        parent_id   2

what i need to do is to construct a multidimensional array based on the id and parent_id provided in each object, please note that the level within the dimension is also provided for each item if this helps.

Im having a real brain blank and cannot figure this one out, please help as i have to find a solution fast.

Thanks in advance.

Answer 1

Since you can have any number of parent_id's at the root level you can end up with multiple trees.

Try this out, good luck:

    var trees:Array = buildTrees(FLAT);

    private static const FLAT:Array =
    [
        {breadcrumb: "{2}", entity_name: "parent 2",
            id:         2,   
            level:      1,   
            parent_id:  0},

        {breadcrumb: "{2,4}", entity_name: "child for parent 2",    
            id:         4,   
            level:      2,   
            parent_id:  2},

        {breadcrumb: "{2,4,5}", entity_name: "child for 4",   
            id:         5,
            level:      3,
            parent_id:  4},

        {breadcrumb: "{2,4,5,7}", entity_name: "child for 5",   
            id:         7,
            level:      4,
            parent_id:  5},

        {breadcrumb: "{2,6}", entity_name: "child 2 for parent 2",
            id:         6,
            level:      2,
            parent_id:  2},

        {breadcrumb: "{2,8}", entity_name: "another child for 2",   
            id:         8,   
            level:      2,
            parent_id:  2},

        {breadcrumb: "{2,9}", entity_name: "another child for 2",   
            id:         9,
            level:      2,
            parent_id:  2}
    ];

    private function buildTrees(flat:Array):Array
    {
        if (!flat.length)
            return null;

        flat.sortOn("parent_id", Array.NUMERIC);

        var trees:Array = new Array();

        var i:uint;

        for (i = 0; i < flat.length; i ++)
        {
            var node:Object = {parent_id: flat[i].parent_id, id: flat[i].id, level: flat[i].level,
                breadcrumb: flat[i].breadcrumb, entity_name: flat[i].entity_name, nodes: new Array()};

            var root:Object = findRoot(flat[i].parent_id, trees);

            if (root) {
                root.nodes.push(node);
            }
            else
                trees.push(node);
        }

        for (i = 0; i < trees.length; i ++)
            sortTree(trees[i]);

        return trees;
    }

    private function findRoot(parent_id:int, trees:Array):Object
    {
        for (var i:uint = 0; i < trees.length; i ++)
        {
            var node:Object = findNode(parent_id, trees[i]);

            if (node)
                return node;
        }

        return null;
    }

    private function findNode(parent_id:int, root:Object):Object
    {
        if (root.id == parent_id)
            return root;

        for (var i:uint = 0; i < root.nodes.length; i ++)
        {
            var node:Object = findNode(parent_id, root.nodes[i]);

            if (node)
                return node;
        }

        return null;
    }

    private function sortTree(root:Object):void
    {
        root.nodes.sortOn("level", Array.NUMERIC);

        for (var i:uint = 0; i < root.nodes.length; i ++)
            sortTree(root.nodes[i]);
    }