import "map";

d3.nest = function() {

var nest = {},

keys = [],

sortKeys = [],

sortValues,

rollup;

function map(mapType, array, depth) {

if (depth >= keys.length) return rollup

? rollup.call(nest, array) : (sortValues

? array.sort(sortValues)

: array);

var i = -1,

n = array.length,

key = keys[depth++],

keyValue,

object,

setter,

valuesByKey = new d3_Map,

values;

while (++i < n) {

if (values = valuesByKey.get(keyValue = key(object = array[i]))) {

values.push(object);

} else {

valuesByKey.set(keyValue, [object]);

}

}

if (mapType) {

object = mapType();

setter = function(keyValue, values) {

object.set(keyValue, map(mapType, values, depth));

};

} else {

object = {};

setter = function(keyValue, values) {

object[keyValue] = map(mapType, values, depth);

};

}

valuesByKey.forEach(setter);

return object;

}

function entries(map, depth) {

if (depth >= keys.length) return map;

var array = [],

sortKey = sortKeys[depth++];

map.forEach(function(key, keyMap) {

array.push({key: key, values: entries(keyMap, depth)});

});

return sortKey

? array.sort(function(a, b) { return sortKey(a.key, b.key); })

: array;

}

nest.map = function(array, mapType) {

return map(mapType, array, 0);

};

nest.entries = function(array) {

return entries(map(d3.map, array, 0), 0);

};

nest.key = function(d) {

keys.push(d);

return nest;

};

// Specifies the order for the most-recently specified key.

// Note: only applies to entries. Map keys are unordered!

nest.sortKeys = function(order) {

sortKeys[keys.length - 1] = order;

return nest;

};

// Specifies the order for leaf values.

// Applies to both maps and entries array.

nest.sortValues = function(order) {

sortValues = order;

return nest;

};

nest.rollup = function(f) {

rollup = f;

return nest;

};

return nest;

};