hkey-algorithm.js

var _ = require('underscore'),
    assert = require('assert');

// This is the input array of hkeys
var input = [
    "0001",
    "0001|0001",
    "0001|0002",
    "0001|0002|0001",
    "0001|0003",
    "0002",
    "0002|0001",
    "0003"
];

// This is the structured object that I want to get out of it
var expected = {
    "0001": {
        "key": "0001",
        "keys": [
            "0001"
        ],
        "children": {
            "0001": {
                "key": "0001|0001",
                "keys": [
                    "0001",
                    "0001"
                ],
                "children": {}
            },
            "0002": {
                "key": "0001|0002",
                "keys": [
                    "0001",
                    "0002"
                ],
                "children": {
                    "0001": {
                        "key": "0001|0002|0001",
                        "keys": [
                            "0001",
                            "0002",
                            "0001"
                        ],
                        "children": {}
                    }
                }
            },
            "0003": {
                "key": "0001|0003",
                "keys": [
                    "0001",
                    "0003"
                ],
                "children": {}
            }
        }
    },
    "0002": {
        "key": "0002",
        "keys": [
            "0002"
        ],
        "children": {
            "0001": {
                "key": "0002|0001",
                "keys": [
                    "0002",
                    "0001"
                ],
                "children": {}
            }
        }
    },
    "0003": {
        "key": "0003",
        "keys": [
            "0003"
        ],
        "children": {}
    }
};
/* 

The expected obj is easier to read in CoffeeScript:

expected:
    "0001":
        "key": "0001"
        "keys": [ "0001" ]
        "children":
            "0001":
                "key": "0001|0001"
                "keys": [ "0001", "0001" ]
                "children": {}
            "0002":
                "key": "0001|0002"
                "keys": [ "0001", "0002" ]
                "children":
                    "0001":
                        "key": "0001|0002|0001"
                        "keys": [ "0001", "0002", "0001" ]
                        "children": {}
            "0003":
                "key": "0001|0003"
                "keys": [ "0001", "0003" ]
                "children": {}
    "0002":
        "key": "0002"
        "keys": [ "0002" ]
        "children": {}
    "0003":
        "key": "0003"
        "keys": [ "0003" ]
        "children": {}
*/

// Start with an empty object
var actual = {};

// Convert the array of strings to an array of objects
input = _.map(input, function (unit) {
    return { key: unit, keys: unit.split("|"), children: {} };
});

// This function is run iteratively in a while loop below
function appendSome(index) {
    // First, make an array of all the input hkeys that have index + 1 segments
    var these = _.filter(input, function (unit) {
        return unit.keys.length === index + 1;
    });

    // Loop through each of those hkeys
    these.forEach(function (unit) {
        // Find the right part of the output object to put this one
        var appendTo = actual;
        for (var j = 0; j < unit.keys.length - 1; j++) {
            appendTo = appendTo[unit.keys[j]].children;
        }
        // Put this hkey where it belongs
        appendTo[unit.keys[unit.keys.length - 1]] = unit;
    });

    // Return the number of hkeys that were found of the proper length. 
    // Once this hits zero, the while loop below will end.
    return these.length;
}

var i = 0,
    left = 10;

// Starting at zero, iterate through the input until there are none left with keys of the desired length
while (left !== 0) {
    left = appendSome(i);
    i++;
}

// Make sure that the output is equal to what I wanted to generate
assert.equal(JSON.stringify(actual), JSON.stringify(expected));

// Log the result
console.log(JSON.stringify(actual, undefined, 4));