Unflatten materialized array

0_unflatten.js

function unflatten(input, delim) {
	var k = [];
	var groups = _.groupBy(input, function (n) {
		var key = n.path.slice(0, n.path.lastIndexOf(n.key));
		if (key.lastIndexOf(delim) === key.length - 1) {
		 	key = key.substr(0, key.length - 1);
		}
		return key;
	});

	function search(items, path) {
		if (!items) return null;
		var result = null;
		for (var i = 0; i < items.length; i++) {
			if (items[i].path === path) {
				result = items[i];
				break;
			}
			result = search(items[i].items, path);
			if (result) break;
		}
		return result;
	}

	_.forEach(groups, function (group, key) {
		for (var i = 0; i < group.length; i++) {
			var element = group[i];
			if (key === '') {
				k.push(element);
			}
			else {
				var parent = search(k, key);
				if (parent) {
					parent.items = parent.items || [];
					parent.items.push(element);
				}
			}
		}
	});
	return k;
}

1_data.js

// input
var delim = '-';
var input = [
	{ key: 'cap', path: 'cap' },
	{ key: 'eap', path: 'cap-eap' },
	{ key: 'hrt', path: 'cap-hrt' },	
	{ key: 'eap', path: 'eap' },
	{ key: 'lkj', path: 'eap-lkj' },
	{ key: 'hrt', path: 'eap-hrt' },
	{ key: 'jkl', path: 'eap-hrt-jkl' },
	{ key: 'rts', path: 'eap-hrt-rts' }
];

// result
/*
[
	{ 
	  key: 'cap', 
	  path: 'cap', 
	  items: [
	    { key: 'eap', path: 'cap-eap' },
	    { key: 'hrt', path: 'cap-hrt' }
	  ]
	},
	{ 
	  key: 'eap', 
	  path: 'eap',
	  items: [
	    { key: 'lkj', path: 'eap-lkj' },
	    { 
	      key: 'hrt', 
	      path: 'eap-hrt',
	      items: [
	        { key: 'jkl', path: ''eap-hrt-jkl' },
	        { key: 'rts', path: ''eap-hrt-rts' }
	      ]
	    }
	  ]
	}
];
*/

2_spec.js

var _ = require('lodash');

describe('Unflatten', function () {

	it('should not blow up with an empty set', function () {
		var data = [];
		var result = unflatten(data, '-');
		expect(result.length).toBe(0);
	});

	it('should find 2 items with no children', function () {
		var data = [
			{ key: 'cap', path: 'cap' },
			{ key: 'eap', path: 'eap' }
		];
		var result = unflatten(data, '-');
		expect(result.length).toBe(2);
		expect(result[0].items || result[1].items).toBe(undefined);
	});

	it('should find one item with 2 children', function () {
		var data = [
			{ key: 'cap', path: 'cap' },
			{ key: 'eap', path: 'cap-eap' },
			{ key: 'hrt', path: 'cap-hrt' },
		];
		var result = unflatten(data, '-');
		expect(result.length).toBe(1);
		expect(result[0].items.length).toBe(2);
	});
	
	it('should find 3 items with 2 children each', function () {
		var data = [
			{ key: 'cap', path: 'cap' },
			{ key: 'eap', path: 'cap-eap' },
			{ key: 'hrt', path: 'cap-hrt' },
			{ key: 'eap', path: 'eap' },
			{ key: 'lkj', path: 'eap-lkj' },
			{ key: 'hrt', path: 'eap-hrt' },
			{ key: 'jkl', path: 'jkl' },
			{ key: 'eap', path: 'jkl-eap' },
			{ key: 'hrt', path: 'jkl-hrt' }
		];
		var result = unflatten(data, '-');
		expect(result.length).toBe(3);
		expect(result[0].items.length).toBe(2);
		expect(result[1].items.length).toBe(2);
		expect(result[2].items.length).toBe(2);
	});
	
	it('should handle deeply nested items', function () {
		var data = [
			{ key: 'cap', path: 'cap' },
			{ key: 'eap', path: 'cap-eap' },
			{ key: 'hrt', path: 'cap-eap-hrt' },
			{ key: 'eap', path: 'cap-eap-hrt-eap' },
			{ key: 'fgh', path: 'cap-eap-hrt-eap-fgh' },
		];
		var result = unflatten(data, '-');
		expect(result.length).toBe(1);
		expect(result[0].items.length).toBe(1);
		expect(result[0].items[0].items.length).toBe(1);
		expect(result[0].items[0].items[0].items.length).toBe(1);
		expect(result[0].items[0].items[0].items[0].items.length).toBe(1);
	});
	
	it('should allow child keys to be named the same as parent keys', function () {
		var data = [
			{ key: 'cap', path: 'cap' },
			{ key: 'cap', path: 'cap-cap' },
			{ key: 'eap', path: 'cap-eap' },
		];
		var result = unflatten(data, '-');
		expect(result.length).toBe(1);
		expect(result[0].items.length).toBe(2);
	});
});