Converting Array of Dictionary to Tree, Org Structure

Converting Array of Dictionary to Tree, Org Structure

Written By: Debasis Das (19-Apr-2015)

The objective of this article is to convert an array of dictionaries (Key value pairs emp_id = some emp id & mgr_id = some emp id) to a single dictionary with an employee with no manager as the root and reportees as children.

The below algorithm although heavy on memory will lead to a faster search path while retrieving a manager and its reportees. The creation of final dictionary takes time and is memory intensive. This is created only for directional view, Implementers need to evaluate this approach thoroughly before implementing this in a production scenario

 

Input is in the form of an array of dictionaries

    emp_id ---- mgr_id
     1000       100
     2000       100
     4000       1000
     4001       1000
     5000       4000
     5001       4000
     6002       5000
     100        NULL // To depict the root

Desired Output should be a single dictionary with 3 key value pairs
Key 1 = emp_id
Key 2 = mgr_id
Key 3 = children Array of Children (each child will be a dictionary having 3 key value pairs)

TreeStructure

Array of Dictionary to Tree – Org Hierarchy Representation

 

The above flat data should finally appear in a single dictionary as follows

/*
 -- 100
    -- 1000
        -- 4000
            -- 5000
                -- 6002
            -- 5001
        -- 4001
    -- 2000
 */

Sample Code

-(void)transformData
{
    NSMutableArray *dataArray = [NSMutableArray new];
//Demo Data Creation to represent the flat data
    [dataArray addObject:@{@"emp_id":@1000,@"mgr_id":@100}];
    [dataArray addObject:@{@"emp_id":@2000,@"mgr_id":@100}];
    [dataArray addObject:@{@"emp_id":@4000,@"mgr_id":@1000}];
    [dataArray addObject:@{@"emp_id":@4001,@"mgr_id":@1000}];
    [dataArray addObject:@{@"emp_id":@5000,@"mgr_id":@4000}];
    [dataArray addObject:@{@"emp_id":@5001,@"mgr_id":@4000}];
    [dataArray addObject:@{@"emp_id":@6002,@"mgr_id":@5000}];
    [dataArray addObject:@{@"emp_id":@100}];
    
    NSMutableDictionary *flatDict = [NSMutableDictionary new];
    for (int i=0; i<dataArray.count; i++)
    {
        [flatDict setObject:[NSMutableDictionary dictionaryWithDictionary:dataArray[i]] forKey:[NSString stringWithFormat:@"id%d",[[[dataArray objectAtIndex:i] objectForKey:@"emp_id"]intValue]]];
    }
    
//At this stage the flat Dict Looks like the following
/*
flatDict {
    id100 =     {
        "emp_id" = 100;
    };
    id1000 =     {
        "emp_id" = 1000;
        "mgr_id" = 100;
    };
    id2000 =     {
        "emp_id" = 2000;
        "mgr_id" = 100;
    };
    id4000 =     {
        "emp_id" = 4000;
        "mgr_id" = 1000;
    };
    id4001 =     {
        "emp_id" = 4001;
        "mgr_id" = 1000;
    };
    id5000 =     {
        "emp_id" = 5000;
        "mgr_id" = 4000;
    };
    id5001 =     {
        "emp_id" = 5001;
        "mgr_id" = 4000;
    };
    id6002 =     {
        "emp_id" = 6002;
        "mgr_id" = 5000;
    };
}
*/

//In the next step,we will add a new mutableArray as the value for a new key called as children    
    for (NSString *key in [flatDict allKeys])
    {
        id obj = [flatDict objectForKey:key];
        [obj setObject:[NSMutableArray new] forKey:@"children"];
    }

//In the below loop all possible combinations are created including the root.
    for (NSString *key in [flatDict allKeys])
    {
        id obj = [flatDict objectForKey:key];
        NSString *mgrId = [NSString stringWithFormat:@"id%d",[[obj objectForKey:@"mgr_id"] intValue]];
        
        if ([flatDict objectForKey:mgrId])
        {
            [[[flatDict objectForKey:mgrId] objectForKey:@"children"] addObject:obj];
        }
    }

//Creating a new root element from the flatDict. The below gets hold of only the root element where the manager id is null    
    NSMutableArray *root = [NSMutableArray new];
    for (NSString *key in [flatDict allKeys])
    {
        id obj = [flatDict objectForKey:key];
        NSString *mgrId = [NSString stringWithFormat:@"id%d",[[obj objectForKey:@"mgr_id"] intValue]];
        if (![flatDict objectForKey:mgrId])
        {
            [root addObject:obj];
        }
    }
    NSLog(@"root %@",root);
}

The final root dictionary looks like the following

    id100 =     {
        children =         (
                        {
                children =                 (
                );
                "emp_id" = 2000;
                "mgr_id" = 100;
            },
                        {
                children =                 (
                                        {
                        children =                         (
                        );
                        "emp_id" = 4001;
                        "mgr_id" = 1000;
                    },
                                        {
                        children =                         (
                                                        {
                                children =                                 (
                                                                        {
                                        children =                                         (
                                        );
                                        "emp_id" = 6002;
                                        "mgr_id" = 5000;
                                    }
                                );
                                "emp_id" = 5000;
                                "mgr_id" = 4000;
                            },
                                                        {
                                children =                                 (
                                );
                                "emp_id" = 5001;
                                "mgr_id" = 4000;
                            }
                        );
                        "emp_id" = 4000;
                        "mgr_id" = 1000;
                    }
                );
                "emp_id" = 1000;
                "mgr_id" = 100;
            }
        );
        "emp_id" = 100;
    };
Posted in algorithms, Cocoa, Objective C Tagged with: , , , ,

Leave a Reply

Your email address will not be published. Required fields are marked *

*

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

Recent Posts


Hit Counter provided by technology news