if (Modernizr.svg){(function() { function d3_class(ctor, properties) { try { for (var key in properties) { Object.defineProperty(ctor.prototype, key, { value: properties[key], enumerable: false }); } } catch (e) { ctor.prototype = properties; } } function d3_arrayCopy(pseudoarray) { var i = -1, n = pseudoarray.length, array = []; while (++i < n) array.push(pseudoarray[i]); return array; } function d3_arraySlice(pseudoarray) { return Array.prototype.slice.call(pseudoarray); } function d3_Map() {} function d3_identity(d) { return d; } function d3_this() { return this; } function d3_true() { return true; } function d3_functor(v) { return typeof v === "function" ? v : function() { return v; }; } function d3_rebind(target, source, method) { return function() { var value = method.apply(source, arguments); return arguments.length ? target : value; }; } function d3_number(x) { return x != null && !isNaN(x); } function d3_zipLength(d) { return d.length; } function d3_splitter(d) { return d == null; } function d3_collapse(s) { return s.trim().replace(/\s+/g, " "); } function d3_range_integerScale(x) { var k = 1; while (x * k % 1) k *= 10; return k; } function d3_dispatch() {} function d3_dispatch_event(dispatch) { function event() { var z = listeners, i = -1, n = z.length, l; while (++i < n) if (l = z[i].on) l.apply(this, arguments); return dispatch; } var listeners = [], listenerByName = new d3_Map; event.on = function(name, listener) { var l = listenerByName.get(name), i; if (arguments.length < 2) return l && l.on; if (l) { l.on = null; listeners = listeners.slice(0, i = listeners.indexOf(l)).concat(listeners.slice(i + 1)); listenerByName.remove(name); } if (listener) listeners.push(listenerByName.set(name, { on: listener })); return dispatch; }; return event; } function d3_format_precision(x, p) { return p - (x ? 1 + Math.floor(Math.log(x + Math.pow(10, 1 + Math.floor(Math.log(x) / Math.LN10) - p)) / Math.LN10) : 1); } function d3_format_typeDefault(x) { return x + ""; } function d3_format_group(value) { var i = value.lastIndexOf("."), f = i >= 0 ? value.substring(i) : (i = value.length, ""), t = []; while (i > 0) t.push(value.substring(i -= 3, i + 3)); return t.reverse().join(",") + f; } function d3_formatPrefix(d, i) { var k = Math.pow(10, Math.abs(8 - i) * 3); return { scale: i > 8 ? function(d) { return d / k; } : function(d) { return d * k; }, symbol: d }; } function d3_ease_clamp(f) { return function(t) { return t <= 0 ? 0 : t >= 1 ? 1 : f(t); }; } function d3_ease_reverse(f) { return function(t) { return 1 - f(1 - t); }; } function d3_ease_reflect(f) { return function(t) { return .5 * (t < .5 ? f(2 * t) : 2 - f(2 - 2 * t)); }; } function d3_ease_identity(t) { return t; } function d3_ease_poly(e) { return function(t) { return Math.pow(t, e); }; } function d3_ease_sin(t) { return 1 - Math.cos(t * Math.PI / 2); } function d3_ease_exp(t) { return Math.pow(2, 10 * (t - 1)); } function d3_ease_circle(t) { return 1 - Math.sqrt(1 - t * t); } function d3_ease_elastic(a, p) { var s; if (arguments.length < 2) p = .45; if (arguments.length < 1) { a = 1; s = p / 4; } else s = p / (2 * Math.PI) * Math.asin(1 / a); return function(t) { return 1 + a * Math.pow(2, 10 * -t) * Math.sin((t - s) * 2 * Math.PI / p); }; } function d3_ease_back(s) { if (!s) s = 1.70158; return function(t) { return t * t * ((s + 1) * t - s); }; } function d3_ease_bounce(t) { return t < 1 / 2.75 ? 7.5625 * t * t : t < 2 / 2.75 ? 7.5625 * (t -= 1.5 / 2.75) * t + .75 : t < 2.5 / 2.75 ? 7.5625 * (t -= 2.25 / 2.75) * t + .9375 : 7.5625 * (t -= 2.625 / 2.75) * t + .984375; } function d3_eventCancel() { d3.event.stopPropagation(); d3.event.preventDefault(); } function d3_eventSource() { var e = d3.event, s; while (s = e.sourceEvent) e = s; return e; } function d3_eventDispatch(target) { var dispatch = new d3_dispatch, i = 0, n = arguments.length; while (++i < n) dispatch[arguments[i]] = d3_dispatch_event(dispatch); dispatch.of = function(thiz, argumentz) { return function(e1) { try { var e0 = e1.sourceEvent = d3.event; e1.target = target; d3.event = e1; dispatch[e1.type].apply(thiz, argumentz); } finally { d3.event = e0; } }; }; return dispatch; } function d3_transform(m) { var r0 = [ m.a, m.b ], r1 = [ m.c, m.d ], kx = d3_transformNormalize(r0), kz = d3_transformDot(r0, r1), ky = d3_transformNormalize(d3_transformCombine(r1, r0, -kz)) || 0; if (r0[0] * r1[1] < r1[0] * r0[1]) { r0[0] *= -1; r0[1] *= -1; kx *= -1; kz *= -1; } this.rotate = (kx ? Math.atan2(r0[1], r0[0]) : Math.atan2(-r1[0], r1[1])) * d3_transformDegrees; this.translate = [ m.e, m.f ]; this.scale = [ kx, ky ]; this.skew = ky ? Math.atan2(kz, ky) * d3_transformDegrees : 0; } function d3_transformDot(a, b) { return a[0] * b[0] + a[1] * b[1]; } function d3_transformNormalize(a) { var k = Math.sqrt(d3_transformDot(a, a)); if (k) { a[0] /= k; a[1] /= k; } return k; } function d3_transformCombine(a, b, k) { a[0] += k * b[0]; a[1] += k * b[1]; return a; } function d3_interpolateByName(name) { return name == "transform" ? d3.interpolateTransform : d3.interpolate; } function d3_uninterpolateNumber(a, b) { b = b - (a = +a) ? 1 / (b - a) : 0; return function(x) { return (x - a) * b; }; } function d3_uninterpolateClamp(a, b) { b = b - (a = +a) ? 1 / (b - a) : 0; return function(x) { return Math.max(0, Math.min(1, (x - a) * b)); }; } function d3_Color() {} function d3_rgb(r, g, b) { return new d3_Rgb(r, g, b); } function d3_Rgb(r, g, b) { this.r = r; this.g = g; this.b = b; } function d3_rgb_hex(v) { return v < 16 ? "0" + Math.max(0, v).toString(16) : Math.min(255, v).toString(16); } function d3_rgb_parse(format, rgb, hsl) { var r = 0, g = 0, b = 0, m1, m2, name; m1 = /([a-z]+)\((.*)\)/i.exec(format); if (m1) { m2 = m1[2].split(","); switch (m1[1]) { case "hsl": { return hsl(parseFloat(m2[0]), parseFloat(m2[1]) / 100, parseFloat(m2[2]) / 100); } case "rgb": { return rgb(d3_rgb_parseNumber(m2[0]), d3_rgb_parseNumber(m2[1]), d3_rgb_parseNumber(m2[2])); } } } if (name = d3_rgb_names.get(format)) return rgb(name.r, name.g, name.b); if (format != null && format.charAt(0) === "#") { if (format.length === 4) { r = format.charAt(1); r += r; g = format.charAt(2); g += g; b = format.charAt(3); b += b; } else if (format.length === 7) { r = format.substring(1, 3); g = format.substring(3, 5); b = format.substring(5, 7); } r = parseInt(r, 16); g = parseInt(g, 16); b = parseInt(b, 16); } return rgb(r, g, b); } function d3_rgb_hsl(r, g, b) { var min = Math.min(r /= 255, g /= 255, b /= 255), max = Math.max(r, g, b), d = max - min, h, s, l = (max + min) / 2; if (d) { s = l < .5 ? d / (max + min) : d / (2 - max - min); if (r == max) h = (g - b) / d + (g < b ? 6 : 0); else if (g == max) h = (b - r) / d + 2; else h = (r - g) / d + 4; h *= 60; } else { s = h = 0; } return d3_hsl(h, s, l); } function d3_rgb_lab(r, g, b) { r = d3_rgb_xyz(r); g = d3_rgb_xyz(g); b = d3_rgb_xyz(b); var x = d3_xyz_lab((.4124564 * r + .3575761 * g + .1804375 * b) / d3_lab_X), y = d3_xyz_lab((.2126729 * r + .7151522 * g + .072175 * b) / d3_lab_Y), z = d3_xyz_lab((.0193339 * r + .119192 * g + .9503041 * b) / d3_lab_Z); return d3_lab(116 * y - 16, 500 * (x - y), 200 * (y - z)); } function d3_rgb_xyz(r) { return (r /= 255) <= .04045 ? r / 12.92 : Math.pow((r + .055) / 1.055, 2.4); } function d3_rgb_parseNumber(c) { var f = parseFloat(c); return c.charAt(c.length - 1) === "%" ? Math.round(f * 2.55) : f; } function d3_hsl(h, s, l) { return new d3_Hsl(h, s, l); } function d3_Hsl(h, s, l) { this.h = h; this.s = s; this.l = l; } function d3_hsl_rgb(h, s, l) { function v(h) { if (h > 360) h -= 360; else if (h < 0) h += 360; if (h < 60) return m1 + (m2 - m1) * h / 60; if (h < 180) return m2; if (h < 240) return m1 + (m2 - m1) * (240 - h) / 60; return m1; } function vv(h) { return Math.round(v(h) * 255); } var m1, m2; h = h % 360; if (h < 0) h += 360; s = s < 0 ? 0 : s > 1 ? 1 : s; l = l < 0 ? 0 : l > 1 ? 1 : l; m2 = l <= .5 ? l * (1 + s) : l + s - l * s; m1 = 2 * l - m2; return d3_rgb(vv(h + 120), vv(h), vv(h - 120)); } function d3_hcl(h, c, l) { return new d3_Hcl(h, c, l); } function d3_Hcl(h, c, l) { this.h = h; this.c = c; this.l = l; } function d3_hcl_lab(h, c, l) { return d3_lab(l, Math.cos(h *= Math.PI / 180) * c, Math.sin(h) * c); } function d3_lab(l, a, b) { return new d3_Lab(l, a, b); } function d3_Lab(l, a, b) { this.l = l; this.a = a; this.b = b; } function d3_lab_rgb(l, a, b) { var y = (l + 16) / 116, x = y + a / 500, z = y - b / 200; x = d3_lab_xyz(x) * d3_lab_X; y = d3_lab_xyz(y) * d3_lab_Y; z = d3_lab_xyz(z) * d3_lab_Z; return d3_rgb(d3_xyz_rgb(3.2404542 * x - 1.5371385 * y - .4985314 * z), d3_xyz_rgb(-.969266 * x + 1.8760108 * y + .041556 * z), d3_xyz_rgb(.0556434 * x - .2040259 * y + 1.0572252 * z)); } function d3_lab_hcl(l, a, b) { return d3_hcl(Math.atan2(b, a) / Math.PI * 180, Math.sqrt(a * a + b * b), l); } function d3_lab_xyz(x) { return x > .206893034 ? x * x * x : (x - 4 / 29) / 7.787037; } function d3_xyz_lab(x) { return x > .008856 ? Math.pow(x, 1 / 3) : 7.787037 * x + 4 / 29; } function d3_xyz_rgb(r) { return Math.round(255 * (r <= .00304 ? 12.92 * r : 1.055 * Math.pow(r, 1 / 2.4) - .055)); } function d3_selection(groups) { d3_arraySubclass(groups, d3_selectionPrototype); return groups; } function d3_selection_selector(selector) { return function() { return d3_select(selector, this); }; } function d3_selection_selectorAll(selector) { return function() { return d3_selectAll(selector, this); }; } function d3_selection_attr(name, value) { function attrNull() { this.removeAttribute(name); } function attrNullNS() { this.removeAttributeNS(name.space, name.local); } function attrConstant() { this.setAttribute(name, value); } function attrConstantNS() { this.setAttributeNS(name.space, name.local, value); } function attrFunction() { var x = value.apply(this, arguments); if (x == null) this.removeAttribute(name); else this.setAttribute(name, x); } function attrFunctionNS() { var x = value.apply(this, arguments); if (x == null) this.removeAttributeNS(name.space, name.local); else this.setAttributeNS(name.space, name.local, x); } name = d3.ns.qualify(name); return value == null ? name.local ? attrNullNS : attrNull : typeof value === "function" ? name.local ? attrFunctionNS : attrFunction : name.local ? attrConstantNS : attrConstant; } function d3_selection_classedRe(name) { return new RegExp("(?:^|\\s+)" + d3.requote(name) + "(?:\\s+|$)", "g"); } function d3_selection_classed(name, value) { function classedConstant() { var i = -1; while (++i < n) name[i](this, value); } function classedFunction() { var i = -1, x = value.apply(this, arguments); while (++i < n) name[i](this, x); } name = name.trim().split(/\s+/).map(d3_selection_classedName); var n = name.length; return typeof value === "function" ? classedFunction : classedConstant; } function d3_selection_classedName(name) { var re = d3_selection_classedRe(name); return function(node, value) { if (c = node.classList) return value ? c.add(name) : c.remove(name); var c = node.className, cb = c.baseVal != null, cv = cb ? c.baseVal : c; if (value) { re.lastIndex = 0; if (!re.test(cv)) { cv = d3_collapse(cv + " " + name); if (cb) c.baseVal = cv; else node.className = cv; } } else if (cv) { cv = d3_collapse(cv.replace(re, " ")); if (cb) c.baseVal = cv; else node.className = cv; } }; } function d3_selection_style(name, value, priority) { function styleNull() { this.style.removeProperty(name); } function styleConstant() { this.style.setProperty(name, value, priority); } function styleFunction() { var x = value.apply(this, arguments); if (x == null) this.style.removeProperty(name); else this.style.setProperty(name, x, priority); } return value == null ? styleNull : typeof value === "function" ? styleFunction : styleConstant; } function d3_selection_property(name, value) { function propertyNull() { delete this[name]; } function propertyConstant() { this[name] = value; } function propertyFunction() { var x = value.apply(this, arguments); if (x == null) delete this[name]; else this[name] = x; } return value == null ? propertyNull : typeof value === "function" ? propertyFunction : propertyConstant; } function d3_selection_dataNode(data) { return { __data__: data }; } function d3_selection_filter(selector) { return function() { return d3_selectMatches(this, selector); }; } function d3_selection_sortComparator(comparator) { if (!arguments.length) comparator = d3.ascending; return function(a, b) { return comparator(a && a.__data__, b && b.__data__); }; } function d3_selection_on(type, listener, capture) { function onRemove() { var wrapper = this[name]; if (wrapper) { this.removeEventListener(type, wrapper, wrapper.$); delete this[name]; } } function onAdd() { function wrapper(e) { var o = d3.event; d3.event = e; args[0] = node.__data__; try { listener.apply(node, args); } finally { d3.event = o; } } var node = this, args = arguments; onRemove.call(this); this.addEventListener(type, this[name] = wrapper, wrapper.$ = capture); wrapper._ = listener; } var name = "__on" + type, i = type.indexOf("."); if (i > 0) type = type.substring(0, i); return listener ? onAdd : onRemove; } function d3_selection_each(groups, callback) { for (var j = 0, m = groups.length; j < m; j++) { for (var group = groups[j], i = 0, n = group.length, node; i < n; i++) { if (node = group[i]) callback(node, i, j); } } return groups; } function d3_selection_enter(selection) { d3_arraySubclass(selection, d3_selection_enterPrototype); return selection; } function d3_transition(groups, id, time) { d3_arraySubclass(groups, d3_transitionPrototype); var tweens = new d3_Map, event = d3.dispatch("start", "end"), ease = d3_transitionEase; groups.id = id; groups.time = time; groups.tween = function(name, tween) { if (arguments.length < 2) return tweens.get(name); if (tween == null) tweens.remove(name); else tweens.set(name, tween); return groups; }; groups.ease = function(value) { if (!arguments.length) return ease; ease = typeof value === "function" ? value : d3.ease.apply(d3, arguments); return groups; }; groups.each = function(type, listener) { if (arguments.length < 2) return d3_transition_each.call(groups, type); event.on(type, listener); return groups; }; d3.timer(function(elapsed) { return d3_selection_each(groups, function(node, i, j) { function start(elapsed) { if (lock.active > id) return stop(); lock.active = id; tweens.forEach(function(key, value) { if (value = value.call(node, d, i)) { tweened.push(value); } }); event.start.call(node, d, i); if (!tick(elapsed)) d3.timer(tick, 0, time); return 1; } function tick(elapsed) { if (lock.active !== id) return stop(); var t = (elapsed - delay) / duration, e = ease(t), n = tweened.length; while (n > 0) { tweened[--n].call(node, e); } if (t >= 1) { stop(); d3_transitionId = id; event.end.call(node, d, i); d3_transitionId = 0; return 1; } } function stop() { if (!--lock.count) delete node.__transition__; return 1; } var tweened = [], delay = node.delay, duration = node.duration, lock = (node = node.node).__transition__ || (node.__transition__ = { active: 0, count: 0 }), d = node.__data__; ++lock.count; delay <= elapsed ? start(elapsed) : d3.timer(start, delay, time); }); }, 0, time); return groups; } function d3_transition_each(callback) { var id = d3_transitionId, ease = d3_transitionEase, delay = d3_transitionDelay, duration = d3_transitionDuration; d3_transitionId = this.id; d3_transitionEase = this.ease(); d3_selection_each(this, function(node, i, j) { d3_transitionDelay = node.delay; d3_transitionDuration = node.duration; callback.call(node = node.node, node.__data__, i, j); }); d3_transitionId = id; d3_transitionEase = ease; d3_transitionDelay = delay; d3_transitionDuration = duration; return this; } function d3_tweenNull(d, i, a) { return a != "" && d3_tweenRemove; } function d3_tweenByName(b, name) { return d3.tween(b, d3_interpolateByName(name)); } function d3_timer_step() { var elapsed, now = Date.now(), t1 = d3_timer_queue; while (t1) { elapsed = now - t1.then; if (elapsed >= t1.delay) t1.flush = t1.callback(elapsed); t1 = t1.next; } var delay = d3_timer_flush() - now; if (delay > 24) { if (isFinite(delay)) { clearTimeout(d3_timer_timeout); d3_timer_timeout = setTimeout(d3_timer_step, delay); } d3_timer_interval = 0; } else { d3_timer_interval = 1; d3_timer_frame(d3_timer_step); } } function d3_timer_flush() { var t0 = null, t1 = d3_timer_queue, then = Infinity; while (t1) { if (t1.flush) { delete d3_timer_byId[t1.callback.id]; t1 = t0 ? t0.next = t1.next : d3_timer_queue = t1.next; } else { then = Math.min(then, t1.then + t1.delay); t1 = (t0 = t1).next; } } return then; } function d3_mousePoint(container, e) { var svg = container.ownerSVGElement || container; if (svg.createSVGPoint) { var point = svg.createSVGPoint(); if (d3_mouse_bug44083 < 0 && (window.scrollX || window.scrollY)) { svg = d3.select(document.body).append("svg").style("position", "absolute").style("top", 0).style("left", 0); var ctm = svg[0][0].getScreenCTM(); d3_mouse_bug44083 = !(ctm.f || ctm.e); svg.remove(); } if (d3_mouse_bug44083) { point.x = e.pageX; point.y = e.pageY; } else { point.x = e.clientX; point.y = e.clientY; } point = point.matrixTransform(container.getScreenCTM().inverse()); return [ point.x, point.y ]; } var rect = container.getBoundingClientRect(); return [ e.clientX - rect.left - container.clientLeft, e.clientY - rect.top - container.clientTop ]; } function d3_noop() {} function d3_scaleExtent(domain) { var start = domain[0], stop = domain[domain.length - 1]; return start < stop ? [ start, stop ] : [ stop, start ]; } function d3_scaleRange(scale) { return scale.rangeExtent ? scale.rangeExtent() : d3_scaleExtent(scale.range()); } function d3_scale_nice(domain, nice) { var i0 = 0, i1 = domain.length - 1, x0 = domain[i0], x1 = domain[i1], dx; if (x1 < x0) { dx = i0, i0 = i1, i1 = dx; dx = x0, x0 = x1, x1 = dx; } if (nice = nice(x1 - x0)) { domain[i0] = nice.floor(x0); domain[i1] = nice.ceil(x1); } return domain; } function d3_scale_niceDefault() { return Math; } function d3_scale_linear(domain, range, interpolate, clamp) { function rescale() { var linear = Math.min(domain.length, range.length) > 2 ? d3_scale_polylinear : d3_scale_bilinear, uninterpolate = clamp ? d3_uninterpolateClamp : d3_uninterpolateNumber; output = linear(domain, range, uninterpolate, interpolate); input = linear(range, domain, uninterpolate, d3.interpolate); return scale; } function scale(x) { return output(x); } var output, input; scale.invert = function(y) { return input(y); }; scale.domain = function(x) { if (!arguments.length) return domain; domain = x.map(Number); return rescale(); }; scale.range = function(x) { if (!arguments.length) return range; range = x; return rescale(); }; scale.rangeRound = function(x) { return scale.range(x).interpolate(d3.interpolateRound); }; scale.clamp = function(x) { if (!arguments.length) return clamp; clamp = x; return rescale(); }; scale.interpolate = function(x) { if (!arguments.length) return interpolate; interpolate = x; return rescale(); }; scale.ticks = function(m) { return d3_scale_linearTicks(domain, m); }; scale.tickFormat = function(m) { return d3_scale_linearTickFormat(domain, m); }; scale.nice = function() { d3_scale_nice(domain, d3_scale_linearNice); return rescale(); }; scale.copy = function() { return d3_scale_linear(domain, range, interpolate, clamp); }; return rescale(); } function d3_scale_linearRebind(scale, linear) { return d3.rebind(scale, linear, "range", "rangeRound", "interpolate", "clamp"); } function d3_scale_linearNice(dx) { dx = Math.pow(10, Math.round(Math.log(dx) / Math.LN10) - 1); return dx && { floor: function(x) { return Math.floor(x / dx) * dx; }, ceil: function(x) { return Math.ceil(x / dx) * dx; } }; } function d3_scale_linearTickRange(domain, m) { var extent = d3_scaleExtent(domain), span = extent[1] - extent[0], step = Math.pow(10, Math.floor(Math.log(span / m) / Math.LN10)), err = m / span * step; if (err <= .15) step *= 10; else if (err <= .35) step *= 5; else if (err <= .75) step *= 2; extent[0] = Math.ceil(extent[0] / step) * step; extent[1] = Math.floor(extent[1] / step) * step + step * .5; extent[2] = step; return extent; } function d3_scale_linearTicks(domain, m) { return d3.range.apply(d3, d3_scale_linearTickRange(domain, m)); } function d3_scale_linearTickFormat(domain, m) { return d3.format(",." + Math.max(0, -Math.floor(Math.log(d3_scale_linearTickRange(domain, m)[2]) / Math.LN10 + .01)) + "f"); } function d3_scale_bilinear(domain, range, uninterpolate, interpolate) { var u = uninterpolate(domain[0], domain[1]), i = interpolate(range[0], range[1]); return function(x) { return i(u(x)); }; } function d3_scale_polylinear(domain, range, uninterpolate, interpolate) { var u = [], i = [], j = 0, k = Math.min(domain.length, range.length) - 1; if (domain[k] < domain[0]) { domain = domain.slice().reverse(); range = range.slice().reverse(); } while (++j <= k) { u.push(uninterpolate(domain[j - 1], domain[j])); i.push(interpolate(range[j - 1], range[j])); } return function(x) { var j = d3.bisect(domain, x, 1, k) - 1; return i[j](u[j](x)); }; } function d3_scale_log(linear, log) { function scale(x) { return linear(log(x)); } var pow = log.pow; scale.invert = function(x) { return pow(linear.invert(x)); }; scale.domain = function(x) { if (!arguments.length) return linear.domain().map(pow); log = x[0] < 0 ? d3_scale_logn : d3_scale_logp; pow = log.pow; linear.domain(x.map(log)); return scale; }; scale.nice = function() { linear.domain(d3_scale_nice(linear.domain(), d3_scale_niceDefault)); return scale; }; scale.ticks = function() { var extent = d3_scaleExtent(linear.domain()), ticks = []; if (extent.every(isFinite)) { var i = Math.floor(extent[0]), j = Math.ceil(extent[1]), u = pow(extent[0]), v = pow(extent[1]); if (log === d3_scale_logn) { ticks.push(pow(i)); for (; i++ < j; ) for (var k = 9; k > 0; k--) ticks.push(pow(i) * k); } else { for (; i < j; i++) for (var k = 1; k < 10; k++) ticks.push(pow(i) * k); ticks.push(pow(i)); } for (i = 0; ticks[i] < u; i++) {} for (j = ticks.length; ticks[j - 1] > v; j--) {} ticks = ticks.slice(i, j); } return ticks; }; scale.tickFormat = function(n, format) { if (arguments.length < 2) format = d3_scale_logFormat; if (arguments.length < 1) return format; var k = Math.max(.1, n / scale.ticks().length), f = log === d3_scale_logn ? (e = -1e-12, Math.floor) : (e = 1e-12, Math.ceil), e; return function(d) { return d / pow(f(log(d) + e)) <= k ? format(d) : ""; }; }; scale.copy = function() { return d3_scale_log(linear.copy(), log); }; return d3_scale_linearRebind(scale, linear); } function d3_scale_logp(x) { return Math.log(x < 0 ? 0 : x) / Math.LN10; } function d3_scale_logn(x) { return -Math.log(x > 0 ? 0 : -x) / Math.LN10; } function d3_scale_pow(linear, exponent) { function scale(x) { return linear(powp(x)); } var powp = d3_scale_powPow(exponent), powb = d3_scale_powPow(1 / exponent); scale.invert = function(x) { return powb(linear.invert(x)); }; scale.domain = function(x) { if (!arguments.length) return linear.domain().map(powb); linear.domain(x.map(powp)); return scale; }; scale.ticks = function(m) { return d3_scale_linearTicks(scale.domain(), m); }; scale.tickFormat = function(m) { return d3_scale_linearTickFormat(scale.domain(), m); }; scale.nice = function() { return scale.domain(d3_scale_nice(scale.domain(), d3_scale_linearNice)); }; scale.exponent = function(x) { if (!arguments.length) return exponent; var domain = scale.domain(); powp = d3_scale_powPow(exponent = x); powb = d3_scale_powPow(1 / exponent); return scale.domain(domain); }; scale.copy = function() { return d3_scale_pow(linear.copy(), exponent); }; return d3_scale_linearRebind(scale, linear); } function d3_scale_powPow(e) { return function(x) { return x < 0 ? -Math.pow(-x, e) : Math.pow(x, e); }; } function d3_scale_ordinal(domain, ranger) { function scale(x) { return range[((index.get(x) || index.set(x, domain.push(x))) - 1) % range.length]; } function steps(start, step) { return d3.range(domain.length).map(function(i) { return start + step * i; }); } var index, range, rangeBand; scale.domain = function(x) { if (!arguments.length) return domain; domain = []; index = new d3_Map; var i = -1, n = x.length, xi; while (++i < n) if (!index.has(xi = x[i])) index.set(xi, domain.push(xi)); return scale[ranger.t].apply(scale, ranger.a); }; scale.range = function(x) { if (!arguments.length) return range; range = x; rangeBand = 0; ranger = { t: "range", a: arguments }; return scale; }; scale.rangePoints = function(x, padding) { if (arguments.length < 2) padding = 0; var start = x[0], stop = x[1], step = (stop - start) / (Math.max(1, domain.length - 1) + padding); range = steps(domain.length < 2 ? (start + stop) / 2 : start + step * padding / 2, step); rangeBand = 0; ranger = { t: "rangePoints", a: arguments }; return scale; }; scale.rangeBands = function(x, padding, outerPadding) { if (arguments.length < 2) padding = 0; if (arguments.length < 3) outerPadding = padding; var reverse = x[1] < x[0], start = x[reverse - 0], stop = x[1 - reverse], step = (stop - start) / (domain.length - padding + 2 * outerPadding); range = steps(start + step * outerPadding, step); if (reverse) range.reverse(); rangeBand = step * (1 - padding); ranger = { t: "rangeBands", a: arguments }; return scale; }; scale.rangeRoundBands = function(x, padding, outerPadding) { if (arguments.length < 2) padding = 0; if (arguments.length < 3) outerPadding = padding; var reverse = x[1] < x[0], start = x[reverse - 0], stop = x[1 - reverse], step = Math.floor((stop - start) / (domain.length - padding + 2 * outerPadding)), error = stop - start - (domain.length - padding) * step; range = steps(start + Math.round(error / 2), step); if (reverse) range.reverse(); rangeBand = Math.round(step * (1 - padding)); ranger = { t: "rangeRoundBands", a: arguments }; return scale; }; scale.rangeBand = function() { return rangeBand; }; scale.rangeExtent = function() { return d3_scaleExtent(ranger.a[0]); }; scale.copy = function() { return d3_scale_ordinal(domain, ranger); }; return scale.domain(domain); } function d3_scale_quantile(domain, range) { function rescale() { var k = 0, n = domain.length, q = range.length; thresholds = []; while (++k < q) thresholds[k - 1] = d3.quantile(domain, k / q); return scale; } function scale(x) { if (isNaN(x = +x)) return NaN; return range[d3.bisect(thresholds, x)]; } var thresholds; scale.domain = function(x) { if (!arguments.length) return domain; domain = x.filter(function(d) { return !isNaN(d); }).sort(d3.ascending); return rescale(); }; scale.range = function(x) { if (!arguments.length) return range; range = x; return rescale(); }; scale.quantiles = function() { return thresholds; }; scale.copy = function() { return d3_scale_quantile(domain, range); }; return rescale(); } function d3_scale_quantize(x0, x1, range) { function scale(x) { return range[Math.max(0, Math.min(i, Math.floor(kx * (x - x0))))]; } function rescale() { kx = range.length / (x1 - x0); i = range.length - 1; return scale; } var kx, i; scale.domain = function(x) { if (!arguments.length) return [ x0, x1 ]; x0 = +x[0]; x1 = +x[x.length - 1]; return rescale(); }; scale.range = function(x) { if (!arguments.length) return range; range = x; return rescale(); }; scale.copy = function() { return d3_scale_quantize(x0, x1, range); }; return rescale(); } function d3_scale_threshold(domain, range) { function scale(x) { return range[d3.bisect(domain, x)]; } scale.domain = function(_) { if (!arguments.length) return domain; domain = _; return scale; }; scale.range = function(_) { if (!arguments.length) return range; range = _; return scale; }; scale.copy = function() { return d3_scale_threshold(domain, range); }; return scale; } function d3_scale_identity(domain) { function identity(x) { return +x; } identity.invert = identity; identity.domain = identity.range = function(x) { if (!arguments.length) return domain; domain = x.map(identity); return identity; }; identity.ticks = function(m) { return d3_scale_linearTicks(domain, m); }; identity.tickFormat = function(m) { return d3_scale_linearTickFormat(domain, m); }; identity.copy = function() { return d3_scale_identity(domain); }; return identity; } function d3_svg_arcInnerRadius(d) { return d.innerRadius; } function d3_svg_arcOuterRadius(d) { return d.outerRadius; } function d3_svg_arcStartAngle(d) { return d.startAngle; } function d3_svg_arcEndAngle(d) { return d.endAngle; } function d3_svg_line(projection) { function line(data) { function segment() { segments.push("M", interpolate(projection(points), tension)); } var segments = [], points = [], i = -1, n = data.length, d, fx = d3_functor(x), fy = d3_functor(y); while (++i < n) { if (defined.call(this, d = data[i], i)) { points.push([ +fx.call(this, d, i), +fy.call(this, d, i) ]); } else if (points.length) { segment(); points = []; } } if (points.length) segment(); return segments.length ? segments.join("") : null; } var x = d3_svg_lineX, y = d3_svg_lineY, defined = d3_true, interpolate = d3_svg_lineLinear, interpolateKey = interpolate.key, tension = .7; line.x = function(_) { if (!arguments.length) return x; x = _; return line; }; line.y = function(_) { if (!arguments.length) return y; y = _; return line; }; line.defined = function(_) { if (!arguments.length) return defined; defined = _; return line; }; line.interpolate = function(_) { if (!arguments.length) return interpolateKey; if (typeof _ === "function") interpolateKey = interpolate = _; else interpolateKey = (interpolate = d3_svg_lineInterpolators.get(_) || d3_svg_lineLinear).key; return line; }; line.tension = function(_) { if (!arguments.length) return tension; tension = _; return line; }; return line; } function d3_svg_lineX(d) { return d[0]; } function d3_svg_lineY(d) { return d[1]; } function d3_svg_lineLinear(points) { return points.join("L"); } function d3_svg_lineLinearClosed(points) { return d3_svg_lineLinear(points) + "Z"; } function d3_svg_lineStepBefore(points) { var i = 0, n = points.length, p = points[0], path = [ p[0], ",", p[1] ]; while (++i < n) path.push("V", (p = points[i])[1], "H", p[0]); return path.join(""); } function d3_svg_lineStepAfter(points) { var i = 0, n = points.length, p = points[0], path = [ p[0], ",", p[1] ]; while (++i < n) path.push("H", (p = points[i])[0], "V", p[1]); return path.join(""); } function d3_svg_lineCardinalOpen(points, tension) { return points.length < 4 ? d3_svg_lineLinear(points) : points[1] + d3_svg_lineHermite(points.slice(1, points.length - 1), d3_svg_lineCardinalTangents(points, tension)); } function d3_svg_lineCardinalClosed(points, tension) { return points.length < 3 ? d3_svg_lineLinear(points) : points[0] + d3_svg_lineHermite((points.push(points[0]), points), d3_svg_lineCardinalTangents([ points[points.length - 2] ].concat(points, [ points[1] ]), tension)); } function d3_svg_lineCardinal(points, tension, closed) { return points.length < 3 ? d3_svg_lineLinear(points) : points[0] + d3_svg_lineHermite(points, d3_svg_lineCardinalTangents(points, tension)); } function d3_svg_lineHermite(points, tangents) { if (tangents.length < 1 || points.length != tangents.length && points.length != tangents.length + 2) { return d3_svg_lineLinear(points); } var quad = points.length != tangents.length, path = "", p0 = points[0], p = points[1], t0 = tangents[0], t = t0, pi = 1; if (quad) { path += "Q" + (p[0] - t0[0] * 2 / 3) + "," + (p[1] - t0[1] * 2 / 3) + "," + p[0] + "," + p[1]; p0 = points[1]; pi = 2; } if (tangents.length > 1) { t = tangents[1]; p = points[pi]; pi++; path += "C" + (p0[0] + t0[0]) + "," + (p0[1] + t0[1]) + "," + (p[0] - t[0]) + "," + (p[1] - t[1]) + "," + p[0] + "," + p[1]; for (var i = 2; i < tangents.length; i++, pi++) { p = points[pi]; t = tangents[i]; path += "S" + (p[0] - t[0]) + "," + (p[1] - t[1]) + "," + p[0] + "," + p[1]; } } if (quad) { var lp = points[pi]; path += "Q" + (p[0] + t[0] * 2 / 3) + "," + (p[1] + t[1] * 2 / 3) + "," + lp[0] + "," + lp[1]; } return path; } function d3_svg_lineCardinalTangents(points, tension) { var tangents = [], a = (1 - tension) / 2, p0, p1 = points[0], p2 = points[1], i = 1, n = points.length; while (++i < n) { p0 = p1; p1 = p2; p2 = points[i]; tangents.push([ a * (p2[0] - p0[0]), a * (p2[1] - p0[1]) ]); } return tangents; } function d3_svg_lineBasis(points) { if (points.length < 3) return d3_svg_lineLinear(points); var i = 1, n = points.length, pi = points[0], x0 = pi[0], y0 = pi[1], px = [ x0, x0, x0, (pi = points[1])[0] ], py = [ y0, y0, y0, pi[1] ], path = [ x0, ",", y0 ]; d3_svg_lineBasisBezier(path, px, py); while (++i < n) { pi = points[i]; px.shift(); px.push(pi[0]); py.shift(); py.push(pi[1]); d3_svg_lineBasisBezier(path, px, py); } i = -1; while (++i < 2) { px.shift(); px.push(pi[0]); py.shift(); py.push(pi[1]); d3_svg_lineBasisBezier(path, px, py); } return path.join(""); } function d3_svg_lineBasisOpen(points) { if (points.length < 4) return d3_svg_lineLinear(points); var path = [], i = -1, n = points.length, pi, px = [ 0 ], py = [ 0 ]; while (++i < 3) { pi = points[i]; px.push(pi[0]); py.push(pi[1]); } path.push(d3_svg_lineDot4(d3_svg_lineBasisBezier3, px) + "," + d3_svg_lineDot4(d3_svg_lineBasisBezier3, py)); --i; while (++i < n) { pi = points[i]; px.shift(); px.push(pi[0]); py.shift(); py.push(pi[1]); d3_svg_lineBasisBezier(path, px, py); } return path.join(""); } function d3_svg_lineBasisClosed(points) { var path, i = -1, n = points.length, m = n + 4, pi, px = [], py = []; while (++i < 4) { pi = points[i % n]; px.push(pi[0]); py.push(pi[1]); } path = [ d3_svg_lineDot4(d3_svg_lineBasisBezier3, px), ",", d3_svg_lineDot4(d3_svg_lineBasisBezier3, py) ]; --i; while (++i < m) { pi = points[i % n]; px.shift(); px.push(pi[0]); py.shift(); py.push(pi[1]); d3_svg_lineBasisBezier(path, px, py); } return path.join(""); } function d3_svg_lineBundle(points, tension) { var n = points.length - 1; if (n) { var x0 = points[0][0], y0 = points[0][1], dx = points[n][0] - x0, dy = points[n][1] - y0, i = -1, p, t; while (++i <= n) { p = points[i]; t = i / n; p[0] = tension * p[0] + (1 - tension) * (x0 + t * dx); p[1] = tension * p[1] + (1 - tension) * (y0 + t * dy); } } return d3_svg_lineBasis(points); } function d3_svg_lineDot4(a, b) { return a[0] * b[0] + a[1] * b[1] + a[2] * b[2] + a[3] * b[3]; } function d3_svg_lineBasisBezier(path, x, y) { path.push("C", d3_svg_lineDot4(d3_svg_lineBasisBezier1, x), ",", d3_svg_lineDot4(d3_svg_lineBasisBezier1, y), ",", d3_svg_lineDot4(d3_svg_lineBasisBezier2, x), ",", d3_svg_lineDot4(d3_svg_lineBasisBezier2, y), ",", d3_svg_lineDot4(d3_svg_lineBasisBezier3, x), ",", d3_svg_lineDot4(d3_svg_lineBasisBezier3, y)); } function d3_svg_lineSlope(p0, p1) { return (p1[1] - p0[1]) / (p1[0] - p0[0]); } function d3_svg_lineFiniteDifferences(points) { var i = 0, j = points.length - 1, m = [], p0 = points[0], p1 = points[1], d = m[0] = d3_svg_lineSlope(p0, p1); while (++i < j) { m[i] = (d + (d = d3_svg_lineSlope(p0 = p1, p1 = points[i + 1]))) / 2; } m[i] = d; return m; } function d3_svg_lineMonotoneTangents(points) { var tangents = [], d, a, b, s, m = d3_svg_lineFiniteDifferences(points), i = -1, j = points.length - 1; while (++i < j) { d = d3_svg_lineSlope(points[i], points[i + 1]); if (Math.abs(d) < 1e-6) { m[i] = m[i + 1] = 0; } else { a = m[i] / d; b = m[i + 1] / d; s = a * a + b * b; if (s > 9) { s = d * 3 / Math.sqrt(s); m[i] = s * a; m[i + 1] = s * b; } } } i = -1; while (++i <= j) { s = (points[Math.min(j, i + 1)][0] - points[Math.max(0, i - 1)][0]) / (6 * (1 + m[i] * m[i])); tangents.push([ s || 0, m[i] * s || 0 ]); } return tangents; } function d3_svg_lineMonotone(points) { return points.length < 3 ? d3_svg_lineLinear(points) : points[0] + d3_svg_lineHermite(points, d3_svg_lineMonotoneTangents(points)); } function d3_svg_lineRadial(points) { var point, i = -1, n = points.length, r, a; while (++i < n) { point = points[i]; r = point[0]; a = point[1] + d3_svg_arcOffset; point[0] = r * Math.cos(a); point[1] = r * Math.sin(a); } return points; } function d3_svg_area(projection) { function area(data) { function segment() { segments.push("M", interpolate(projection(points1), tension), L, interpolateReverse(projection(points0.reverse()), tension), "Z"); } var segments = [], points0 = [], points1 = [], i = -1, n = data.length, d, fx0 = d3_functor(x0), fy0 = d3_functor(y0), fx1 = x0 === x1 ? function() { return x; } : d3_functor(x1), fy1 = y0 === y1 ? function() { return y; } : d3_functor(y1), x, y; while (++i < n) { if (defined.call(this, d = data[i], i)) { points0.push([ x = +fx0.call(this, d, i), y = +fy0.call(this, d, i) ]); points1.push([ +fx1.call(this, d, i), +fy1.call(this, d, i) ]); } else if (points0.length) { segment(); points0 = []; points1 = []; } } if (points0.length) segment(); return segments.length ? segments.join("") : null; } var x0 = d3_svg_lineX, x1 = d3_svg_lineX, y0 = 0, y1 = d3_svg_lineY, defined = d3_true, interpolate = d3_svg_lineLinear, interpolateKey = interpolate.key, interpolateReverse = interpolate, L = "L", tension = .7; area.x = function(_) { if (!arguments.length) return x1; x0 = x1 = _; return area; }; area.x0 = function(_) { if (!arguments.length) return x0; x0 = _; return area; }; area.x1 = function(_) { if (!arguments.length) return x1; x1 = _; return area; }; area.y = function(_) { if (!arguments.length) return y1; y0 = y1 = _; return area; }; area.y0 = function(_) { if (!arguments.length) return y0; y0 = _; return area; }; area.y1 = function(_) { if (!arguments.length) return y1; y1 = _; return area; }; area.defined = function(_) { if (!arguments.length) return defined; defined = _; return area; }; area.interpolate = function(_) { if (!arguments.length) return interpolateKey; if (typeof _ === "function") interpolateKey = interpolate = _; else interpolateKey = (interpolate = d3_svg_lineInterpolators.get(_) || d3_svg_lineLinear).key; interpolateReverse = interpolate.reverse || interpolate; L = interpolate.closed ? "M" : "L"; return area; }; area.tension = function(_) { if (!arguments.length) return tension; tension = _; return area; }; return area; } function d3_svg_chordSource(d) { return d.source; } function d3_svg_chordTarget(d) { return d.target; } function d3_svg_chordRadius(d) { return d.radius; } function d3_svg_chordStartAngle(d) { return d.startAngle; } function d3_svg_chordEndAngle(d) { return d.endAngle; } function d3_svg_diagonalProjection(d) { return [ d.x, d.y ]; } function d3_svg_diagonalRadialProjection(projection) { return function() { var d = projection.apply(this, arguments), r = d[0], a = d[1] + d3_svg_arcOffset; return [ r * Math.cos(a), r * Math.sin(a) ]; }; } function d3_svg_symbolSize() { return 64; } function d3_svg_symbolType() { return "circle"; } function d3_svg_symbolCircle(size) { var r = Math.sqrt(size / Math.PI); return "M0," + r + "A" + r + "," + r + " 0 1,1 0," + -r + "A" + r + "," + r + " 0 1,1 0," + r + "Z"; } function d3_svg_axisX(selection, x) { selection.attr("transform", function(d) { return "translate(" + x(d) + ",0)"; }); } function d3_svg_axisY(selection, y) { selection.attr("transform", function(d) { return "translate(0," + y(d) + ")"; }); } function d3_svg_axisSubdivide(scale, ticks, m) { subticks = []; if (m && ticks.length > 1) { var extent = d3_scaleExtent(scale.domain()), subticks, i = -1, n = ticks.length, d = (ticks[1] - ticks[0]) / ++m, j, v; while (++i < n) { for (j = m; --j > 0; ) { if ((v = +ticks[i] - j * d) >= extent[0]) { subticks.push(v); } } } for (--i, j = 0; ++j < m && (v = +ticks[i] + j * d) < extent[1]; ) { subticks.push(v); } } return subticks; } function d3_behavior_zoomDelta() { if (!d3_behavior_zoomDiv) { d3_behavior_zoomDiv = d3.select("body").append("div").style("visibility", "hidden").style("top", 0).style("height", 0).style("width", 0).style("overflow-y", "scroll").append("div").style("height", "2000px").node().parentNode; } var e = d3.event, delta; try { d3_behavior_zoomDiv.scrollTop = 1e3; d3_behavior_zoomDiv.dispatchEvent(e); delta = 1e3 - d3_behavior_zoomDiv.scrollTop; } catch (error) { delta = e.wheelDelta || -e.detail * 5; } return delta; } function d3_layout_bundlePath(link) { var start = link.source, end = link.target, lca = d3_layout_bundleLeastCommonAncestor(start, end), points = [ start ]; while (start !== lca) { start = start.parent; points.push(start); } var k = points.length; while (end !== lca) { points.splice(k, 0, end); end = end.parent; } return points; } function d3_layout_bundleAncestors(node) { var ancestors = [], parent = node.parent; while (parent != null) { ancestors.push(node); node = parent; parent = parent.parent; } ancestors.push(node); return ancestors; } function d3_layout_bundleLeastCommonAncestor(a, b) { if (a === b) return a; var aNodes = d3_layout_bundleAncestors(a), bNodes = d3_layout_bundleAncestors(b), aNode = aNodes.pop(), bNode = bNodes.pop(), sharedNode = null; while (aNode === bNode) { sharedNode = aNode; aNode = aNodes.pop(); bNode = bNodes.pop(); } return sharedNode; } function d3_layout_forceDragstart(d) { d.fixed |= 2; } function d3_layout_forceDragend(d) { d.fixed &= 1; } function d3_layout_forceMouseover(d) { d.fixed |= 4; } function d3_layout_forceMouseout(d) { d.fixed &= 3; } function d3_layout_forceAccumulate(quad, alpha, charges) { var cx = 0, cy = 0; quad.charge = 0; if (!quad.leaf) { var nodes = quad.nodes, n = nodes.length, i = -1, c; while (++i < n) { c = nodes[i]; if (c == null) continue; d3_layout_forceAccumulate(c, alpha, charges); quad.charge += c.charge; cx += c.charge * c.cx; cy += c.charge * c.cy; } } if (quad.point) { if (!quad.leaf) { quad.point.x += Math.random() - .5; quad.point.y += Math.random() - .5; } var k = alpha * charges[quad.point.index]; quad.charge += quad.pointCharge = k; cx += k * quad.point.x; cy += k * quad.point.y; } quad.cx = cx / quad.charge; quad.cy = cy / quad.charge; } function d3_layout_forceLinkDistance(link) { return 20; } function d3_layout_forceLinkStrength(link) { return 1; } function d3_layout_stackX(d) { return d.x; } function d3_layout_stackY(d) { return d.y; } function d3_layout_stackOut(d, y0, y) { d.y0 = y0; d.y = y; } function d3_layout_stackOrderDefault(data) { return d3.range(data.length); } function d3_layout_stackOffsetZero(data) { var j = -1, m = data[0].length, y0 = []; while (++j < m) y0[j] = 0; return y0; } function d3_layout_stackMaxIndex(array) { var i = 1, j = 0, v = array[0][1], k, n = array.length; for (; i < n; ++i) { if ((k = array[i][1]) > v) { j = i; v = k; } } return j; } function d3_layout_stackReduceSum(d) { return d.reduce(d3_layout_stackSum, 0); } function d3_layout_stackSum(p, d) { return p + d[1]; } function d3_layout_histogramBinSturges(range, values) { return d3_layout_histogramBinFixed(range, Math.ceil(Math.log(values.length) / Math.LN2 + 1)); } function d3_layout_histogramBinFixed(range, n) { var x = -1, b = +range[0], m = (range[1] - b) / n, f = []; while (++x <= n) f[x] = m * x + b; return f; } function d3_layout_histogramRange(values) { return [ d3.min(values), d3.max(values) ]; } function d3_layout_hierarchyRebind(object, hierarchy) { d3.rebind(object, hierarchy, "sort", "children", "value"); object.links = d3_layout_hierarchyLinks; object.nodes = function(d) { d3_layout_hierarchyInline = true; return (object.nodes = object)(d); }; return object; } function d3_layout_hierarchyChildren(d) { return d.children; } function d3_layout_hierarchyValue(d) { return d.value; } function d3_layout_hierarchySort(a, b) { return b.value - a.value; } function d3_layout_hierarchyLinks(nodes) { return d3.merge(nodes.map(function(parent) { return (parent.children || []).map(function(child) { return { source: parent, target: child }; }); })); } function d3_layout_packSort(a, b) { return a.value - b.value; } function d3_layout_packInsert(a, b) { var c = a._pack_next; a._pack_next = b; b._pack_prev = a; b._pack_next = c; c._pack_prev = b; } function d3_layout_packSplice(a, b) { a._pack_next = b; b._pack_prev = a; } function d3_layout_packIntersects(a, b) { var dx = b.x - a.x, dy = b.y - a.y, dr = a.r + b.r; return dr * dr - dx * dx - dy * dy > .001; } function d3_layout_packSiblings(node) { function bound(node) { xMin = Math.min(node.x - node.r, xMin); xMax = Math.max(node.x + node.r, xMax); yMin = Math.min(node.y - node.r, yMin); yMax = Math.max(node.y + node.r, yMax); } if (!(nodes = node.children) || !(n = nodes.length)) return; var nodes, xMin = Infinity, xMax = -Infinity, yMin = Infinity, yMax = -Infinity, a, b, c, i, j, k, n; nodes.forEach(d3_layout_packLink); a = nodes[0]; a.x = -a.r; a.y = 0; bound(a); if (n > 1) { b = nodes[1]; b.x = b.r; b.y = 0; bound(b); if (n > 2) { c = nodes[2]; d3_layout_packPlace(a, b, c); bound(c); d3_layout_packInsert(a, c); a._pack_prev = c; d3_layout_packInsert(c, b); b = a._pack_next; for (i = 3; i < n; i++) { d3_layout_packPlace(a, b, c = nodes[i]); var isect = 0, s1 = 1, s2 = 1; for (j = b._pack_next; j !== b; j = j._pack_next, s1++) { if (d3_layout_packIntersects(j, c)) { isect = 1; break; } } if (isect == 1) { for (k = a._pack_prev; k !== j._pack_prev; k = k._pack_prev, s2++) { if (d3_layout_packIntersects(k, c)) { break; } } } if (isect) { if (s1 < s2 || s1 == s2 && b.r < a.r) d3_layout_packSplice(a, b = j); else d3_layout_packSplice(a = k, b); i--; } else { d3_layout_packInsert(a, c); b = c; bound(c); } } } } var cx = (xMin + xMax) / 2, cy = (yMin + yMax) / 2, cr = 0; for (i = 0; i < n; i++) { c = nodes[i]; c.x -= cx; c.y -= cy; cr = Math.max(cr, c.r + Math.sqrt(c.x * c.x + c.y * c.y)); } node.r = cr; nodes.forEach(d3_layout_packUnlink); } function d3_layout_packLink(node) { node._pack_next = node._pack_prev = node; } function d3_layout_packUnlink(node) { delete node._pack_next; delete node._pack_prev; } function d3_layout_packTransform(node, x, y, k) { var children = node.children; node.x = x += k * node.x; node.y = y += k * node.y; node.r *= k; if (children) { var i = -1, n = children.length; while (++i < n) d3_layout_packTransform(children[i], x, y, k); } } function d3_layout_packPlace(a, b, c) { var db = a.r + c.r, dx = b.x - a.x, dy = b.y - a.y; if (db && (dx || dy)) { var da = b.r + c.r, dc = dx * dx + dy * dy; da *= da; db *= db; var x = .5 + (db - da) / (2 * dc), y = Math.sqrt(Math.max(0, 2 * da * (db + dc) - (db -= dc) * db - da * da)) / (2 * dc); c.x = a.x + x * dx + y * dy; c.y = a.y + x * dy - y * dx; } else { c.x = a.x + db; c.y = a.y; } } function d3_layout_clusterY(children) { return 1 + d3.max(children, function(child) { return child.y; }); } function d3_layout_clusterX(children) { return children.reduce(function(x, child) { return x + child.x; }, 0) / children.length; } function d3_layout_clusterLeft(node) { var children = node.children; return children && children.length ? d3_layout_clusterLeft(children[0]) : node; } function d3_layout_clusterRight(node) { var children = node.children, n; return children && (n = children.length) ? d3_layout_clusterRight(children[n - 1]) : node; } function d3_layout_treeSeparation(a, b) { return a.parent == b.parent ? 1 : 2; } function d3_layout_treeLeft(node) { var children = node.children; return children && children.length ? children[0] : node._tree.thread; } function d3_layout_treeRight(node) { var children = node.children, n; return children && (n = children.length) ? children[n - 1] : node._tree.thread; } function d3_layout_treeSearch(node, compare) { var children = node.children; if (children && (n = children.length)) { var child, n, i = -1; while (++i < n) { if (compare(child = d3_layout_treeSearch(children[i], compare), node) > 0) { node = child; } } } return node; } function d3_layout_treeRightmost(a, b) { return a.x - b.x; } function d3_layout_treeLeftmost(a, b) { return b.x - a.x; } function d3_layout_treeDeepest(a, b) { return a.depth - b.depth; } function d3_layout_treeVisitAfter(node, callback) { function visit(node, previousSibling) { var children = node.children; if (children && (n = children.length)) { var child, previousChild = null, i = -1, n; while (++i < n) { child = children[i]; visit(child, previousChild); previousChild = child; } } callback(node, previousSibling); } visit(node, null); } function d3_layout_treeShift(node) { var shift = 0, change = 0, children = node.children, i = children.length, child; while (--i >= 0) { child = children[i]._tree; child.prelim += shift; child.mod += shift; shift += child.shift + (change += child.change); } } function d3_layout_treeMove(ancestor, node, shift) { ancestor = ancestor._tree; node = node._tree; var change = shift / (node.number - ancestor.number); ancestor.change += change; node.change -= change; node.shift += shift; node.prelim += shift; node.mod += shift; } function d3_layout_treeAncestor(vim, node, ancestor) { return vim._tree.ancestor.parent == node.parent ? vim._tree.ancestor : ancestor; } function d3_layout_treemapPadNull(node) { return { x: node.x, y: node.y, dx: node.dx, dy: node.dy }; } function d3_layout_treemapPad(node, padding) { var x = node.x + padding[3], y = node.y + padding[0], dx = node.dx - padding[1] - padding[3], dy = node.dy - padding[0] - padding[2]; if (dx < 0) { x += dx / 2; dx = 0; } if (dy < 0) { y += dy / 2; dy = 0; } return { x: x, y: y, dx: dx, dy: dy }; } function d3_dsv(delimiter, mimeType) { function dsv(url, callback) { d3.text(url, mimeType, function(text) { callback(text && dsv.parse(text)); }); } function formatRow(row) { return row.map(formatValue).join(delimiter); } function formatValue(text) { return reFormat.test(text) ? '"' + text.replace(/\"/g, '""') + '"' : text; } var reParse = new RegExp("\r\n|[" + delimiter + "\r\n]", "g"), reFormat = new RegExp('["' + delimiter + "\n]"), delimiterCode = delimiter.charCodeAt(0); dsv.parse = function(text) { var header; return dsv.parseRows(text, function(row, i) { if (i) { var o = {}, j = -1, m = header.length; while (++j < m) o[header[j]] = row[j]; return o; } else { header = row; return null; } }); }; dsv.parseRows = function(text, f) { function token() { if (reParse.lastIndex >= text.length) return EOF; if (eol) { eol = false; return EOL; } var j = reParse.lastIndex; if (text.charCodeAt(j) === 34) { var i = j; while (i++ < text.length) { if (text.charCodeAt(i) === 34) { if (text.charCodeAt(i + 1) !== 34) break; i++; } } reParse.lastIndex = i + 2; var c = text.charCodeAt(i + 1); if (c === 13) { eol = true; if (text.charCodeAt(i + 2) === 10) reParse.lastIndex++; } else if (c === 10) { eol = true; } return text.substring(j + 1, i).replace(/""/g, '"'); } var m = reParse.exec(text); if (m) { eol = m[0].charCodeAt(0) !== delimiterCode; return text.substring(j, m.index); } reParse.lastIndex = text.length; return text.substring(j); } var EOL = {}, EOF = {}, rows = [], n = 0, t, eol; reParse.lastIndex = 0; while ((t = token()) !== EOF) { var a = []; while (t !== EOL && t !== EOF) { a.push(t); t = token(); } if (f && !(a = f(a, n++))) continue; rows.push(a); } return rows; }; dsv.format = function(rows) { return rows.map(formatRow).join("\n"); }; return dsv; } function d3_geo_type(types, defaultValue) { return function(object) { return object && types.hasOwnProperty(object.type) ? types[object.type](object) : defaultValue; }; } function d3_path_circle(radius) { return "m0," + radius + "a" + radius + "," + radius + " 0 1,1 0," + -2 * radius + "a" + radius + "," + radius + " 0 1,1 0," + +2 * radius + "z"; } function d3_geo_bounds(o, f) { if (d3_geo_boundsTypes.hasOwnProperty(o.type)) d3_geo_boundsTypes[o.type](o, f); } function d3_geo_boundsFeature(o, f) { d3_geo_bounds(o.geometry, f); } function d3_geo_boundsFeatureCollection(o, f) { for (var a = o.features, i = 0, n = a.length; i < n; i++) { d3_geo_bounds(a[i].geometry, f); } } function d3_geo_boundsGeometryCollection(o, f) { for (var a = o.geometries, i = 0, n = a.length; i < n; i++) { d3_geo_bounds(a[i], f); } } function d3_geo_boundsLineString(o, f) { for (var a = o.coordinates, i = 0, n = a.length; i < n; i++) { f.apply(null, a[i]); } } function d3_geo_boundsMultiLineString(o, f) { for (var a = o.coordinates, i = 0, n = a.length; i < n; i++) { for (var b = a[i], j = 0, m = b.length; j < m; j++) { f.apply(null, b[j]); } } } function d3_geo_boundsMultiPolygon(o, f) { for (var a = o.coordinates, i = 0, n = a.length; i < n; i++) { for (var b = a[i][0], j = 0, m = b.length; j < m; j++) { f.apply(null, b[j]); } } } function d3_geo_boundsPoint(o, f) { f.apply(null, o.coordinates); } function d3_geo_boundsPolygon(o, f) { for (var a = o.coordinates[0], i = 0, n = a.length; i < n; i++) { f.apply(null, a[i]); } } function d3_geo_greatArcSource(d) { return d.source; } function d3_geo_greatArcTarget(d) { return d.target; } function d3_geo_greatArcInterpolator() { function interpolate(t) { var B = Math.sin(t *= d) * k, A = Math.sin(d - t) * k, x = A * kx0 + B * kx1, y = A * ky0 + B * ky1, z = A * sy0 + B * sy1; return [ Math.atan2(y, x) / d3_geo_radians, Math.atan2(z, Math.sqrt(x * x + y * y)) / d3_geo_radians ]; } var x0, y0, cy0, sy0, kx0, ky0, x1, y1, cy1, sy1, kx1, ky1, d, k; interpolate.distance = function() { if (d == null) k = 1 / Math.sin(d = Math.acos(Math.max(-1, Math.min(1, sy0 * sy1 + cy0 * cy1 * Math.cos(x1 - x0))))); return d; }; interpolate.source = function(_) { var cx0 = Math.cos(x0 = _[0] * d3_geo_radians), sx0 = Math.sin(x0); cy0 = Math.cos(y0 = _[1] * d3_geo_radians); sy0 = Math.sin(y0); kx0 = cy0 * cx0; ky0 = cy0 * sx0; d = null; return interpolate; }; interpolate.target = function(_) { var cx1 = Math.cos(x1 = _[0] * d3_geo_radians), sx1 = Math.sin(x1); cy1 = Math.cos(y1 = _[1] * d3_geo_radians); sy1 = Math.sin(y1); kx1 = cy1 * cx1; ky1 = cy1 * sx1; d = null; return interpolate; }; return interpolate; } function d3_geo_greatArcInterpolate(a, b) { var i = d3_geo_greatArcInterpolator().source(a).target(b); i.distance(); return i; } function d3_geom_contourStart(grid) { var x = 0, y = 0; while (true) { if (grid(x, y)) { return [ x, y ]; } if (x === 0) { x = y + 1; y = 0; } else { x = x - 1; y = y + 1; } } } function d3_geom_hullCCW(i1, i2, i3, v) { var t, a, b, c, d, e, f; t = v[i1]; a = t[0]; b = t[1]; t = v[i2]; c = t[0]; d = t[1]; t = v[i3]; e = t[0]; f = t[1]; return (f - b) * (c - a) - (d - b) * (e - a) > 0; } function d3_geom_polygonInside(p, a, b) { return (b[0] - a[0]) * (p[1] - a[1]) < (b[1] - a[1]) * (p[0] - a[0]); } function d3_geom_polygonIntersect(c, d, a, b) { var x1 = c[0], x2 = d[0], x3 = a[0], x4 = b[0], y1 = c[1], y2 = d[1], y3 = a[1], y4 = b[1], x13 = x1 - x3, x21 = x2 - x1, x43 = x4 - x3, y13 = y1 - y3, y21 = y2 - y1, y43 = y4 - y3, ua = (x43 * y13 - y43 * x13) / (y43 * x21 - x43 * y21); return [ x1 + ua * x21, y1 + ua * y21 ]; } function d3_voronoi_tessellate(vertices, callback) { var Sites = { list: vertices.map(function(v, i) { return { index: i, x: v[0], y: v[1] }; }).sort(function(a, b) { return a.y < b.y ? -1 : a.y > b.y ? 1 : a.x < b.x ? -1 : a.x > b.x ? 1 : 0; }), bottomSite: null }; var EdgeList = { list: [], leftEnd: null, rightEnd: null, init: function() { EdgeList.leftEnd = EdgeList.createHalfEdge(null, "l"); EdgeList.rightEnd = EdgeList.createHalfEdge(null, "l"); EdgeList.leftEnd.r = EdgeList.rightEnd; EdgeList.rightEnd.l = EdgeList.leftEnd; EdgeList.list.unshift(EdgeList.leftEnd, EdgeList.rightEnd); }, createHalfEdge: function(edge, side) { return { edge: edge, side: side, vertex: null, l: null, r: null }; }, insert: function(lb, he) { he.l = lb; he.r = lb.r; lb.r.l = he; lb.r = he; }, leftBound: function(p) { var he = EdgeList.leftEnd; do { he = he.r; } while (he != EdgeList.rightEnd && Geom.rightOf(he,