Hierarchy Data shift

Question

After running a recursive function to obtain an employee/manager family tree - a further requirement has come up to reserve an overall manager structure.

So I would imagine the input array to look something like this

[["Employee A", "1000", "Employee B", "1001", "Employee C", "1002"],
["Employee D", "1003", "Employee C", "1002"]]

and the output array would need to look like this

[["Employee A", "1000", "Employee B", "1001", "Employee C", "1002"],
["Employee D", "1003", null, null, "Employee C", "1002"]]

The hierachy needs to be sorted in this manner to show that Employee C retains the role of senior manager at all times

public void refactorArray(String jsonData) throws Exception {
    JSONArray array = new JSONArray(jsonData);
    for (int i = 0; i < array.length(); i++) {

        //flag previous position of grandfather manager and name/id

        // if previous position does not match current position - do logic to pop the array at that element to put it back into the previous position
    }
}

Answer 1

Building on the idea of finding the longest one first, and taking it as reference for future boss-padding, yields the following code, which works fine for the case above.

The idea is to build a 'bosses' lookup table, built from the longest leaf-to-root path we find. Whenever we have a boss that is in the lookup table, we make sure that he appears in the same position as he appears in the longest path, padding with nulls as necessary.

import org.json.JSONArray;
import java.util.ArrayList;
import java.util.HashMap;

public class T {
    static String refactor(String jsonData) {
        JSONArray array = new JSONArray(jsonData);

        // find longest array in original container
        JSONArray longest = null;
        for (int i=0; i<array.length(); i++) {
            JSONArray a = array.getJSONArray(i);
            if (longest == null || a.length() > longest.length()) {
                longest = a;
            }
        }

        // build a map with the people in "longest", for quick lookup
        HashMap<String, Integer> bosses = new HashMap<String, Integer>();
        for (int i=0; i<longest.length(); i+=2) {
            bosses.put(longest.getString(i) + "|" + longest.getString(i+1), i);
        }

        // prepare target container       
        ArrayList<JSONArray> container = new ArrayList<JSONArray>();

        // fill in missing values
        for (int i=0; i<array.length(); i++) {
            JSONArray a = array.getJSONArray(i);
            ArrayList<String> refactored = new ArrayList<String>();
            // copy leaf employee
            refactored.add(a.getString(0));
            refactored.add(a.getString(1));
            for (int j=2; j<a.length(); j+=2) {
                // possibly fill in nulls before adding this boss
                String boss = a.getString(j) + "|" + a.getString(j+1);
                if (bosses.containsKey(boss)) {
                    for (int k=j; k<bosses.get(boss); k++) {
                        // pad with nulls until we reach target position
                        refactored.add(null);
                    }
                }
                refactored.add(a.getString(j));
                refactored.add(a.getString(j+1));
            }
            container.add(new JSONArray(refactored));
        }
        return new JSONArray(container).toString();
    }

    public static void main(String args[]) {
        System.out.println(refactor(args[0]));
    }
}

Answer 2

This is the first loop - it seems to provide the rule correctly. I've written in javascript here -

************** LATEST CODE ********************* 17/04/2015

http://jsfiddle.net/y74z42ms/25/

For loop 2 - am I to loop through each array element and rule - and if so what logic is applied to insert a null entry?

--- does this look correct?

var input = [
    ["AaronG", "RupertJ", "ScottK", "DannyC", "LennyD"],
    ["JackieP", "RupertJ", "ScottK", "DannyC", "LennyD"],
    ["NelsaI", "SamJ", "ScottK", "DannyC", "LennyD"],
    ["BrentD", "SamJ", "ScottK", "DannyC", "LennyD"],
    ["MaryS", "CardinalE", "DannyC", "LennyD"],
    ["GaroleP", "CardinalE", "DannyC","LennyD"],
    ["AlanA", "ChanA", "KopecK", "LennyD"],
    ["GerryA", "ChanA", "KopecK", "LennyD"],
    ["BurlS", "TodD", "KopecK", "LennyD"],
    ["KenS", "TodD", "KopecK", "LennyD"],
    ["JerryU", "JasonA", "JefferyW", "MargotS", "LennyD"],
    ["BakerI", "JasonA", "JefferyW", "MargotS", "LennyD"]
];
console.log("input", input);
$('#in').html(input.toString());

//:loop1
var ruleStorage = [];
var rule = null;
var lastRule = null;
for (i = 0; i < input.length; i++) {
    //count the nested array elements - store it if its the longest
    rule = input[i];
    if (lastRule != null) {
        if (lastRule.length > rule.length) {
            rule = lastRule;
        } 
            ruleStorage.push(rule);    
    }
    lastRule = rule;
}

ruleStorage = $.unique(ruleStorage); //provides unique rules
//:loop1


//:loop2
//use rule 1
console.log("ruleStorage", ruleStorage);
rule = ruleStorage[0];
var output = [];
for (i = 0; i < input.length; i++) {
    //count the nested array elements - store it if its the longest
    var nestedEl = input[i];
    var newNest = [];
    //compare nestedEl with rule - and use the rule to insert null spaces accordingly

    //create null entries first
    for (j = 0; j < rule.length; j++) {
        newNest[j] = null;
    }

    //loop through the rule and compare
    for (j = 0; j < rule.length; j++) {
        var originalPos = rule.indexOf(rule[j]);
        var currentPos = nestedEl.indexOf(rule[j]);

        //build the new nest
        //if its in the original postion restore it as such
        if (originalPos == currentPos) {
            newNest[j] = nestedEl[j];
        }

        //element is new and doesn't exist in the rule
        if (
        currentPos == -1 && originalPos != -1 && rule.indexOf(nestedEl[j]) == -1 && nestedEl[j] !== undefined) {
            newNest[originalPos] = nestedEl[j];
        }

        //element is not new but its in the wrong place
        if (
        rule.indexOf(nestedEl[j]) != -1 && nestedEl[j] !== undefined) {
            var rulePos = rule.indexOf(nestedEl[j]);
            newNest[rulePos] = nestedEl[j];
        }

    }
    //console.log("newNest", newNest);
    //console.log("nestedEl", nestedEl);

    output.push(newNest);

}
console.log("output", output);

$('#out').html(output.toString());
//:loop2

Answer 3

You can do it in two loops,

Loop1: find the longest array in the wrapper array. It would be the complete path from lowest position to big boss. Take this as the ruler. There could be more than one longest array, depending on your requirements.

Loop2: for each array, compare elements with the rule we found, when a unmatched element was found, add a null (or two Nulls with ID) element.

btw, List would be better Datastructure than array(s) for this problem.

input:

a-b-c-d-e-f
x-c-e
y-b-d-f

1st step you found a-b-c-d-e-f

then compare x-c-e to it in each element from the 2nd element, you get x-null-c-null-e-null