1f2cc30ac3cb12bbce52456c0e5cfc1be5540234
[rails.git] / vendor / assets / iD / iD.js
1 (function(exports) {
2
3   var bootstrap = (typeof exports.bootstrap === "object") ?
4     exports.bootstrap :
5     (exports.bootstrap = {});
6
7   bootstrap.tooltip = function() {
8
9     var tooltip = function(selection) {
10         selection.each(setup);
11       },
12       animation = d3.functor(false),
13       html = d3.functor(false),
14       title = function() {
15         var title = this.getAttribute("data-original-title");
16         if (title) {
17           return title;
18         } else {
19           title = this.getAttribute("title");
20           this.removeAttribute("title");
21           this.setAttribute("data-original-title", title);
22         }
23         return title;
24       },
25       over = "mouseenter.tooltip",
26       out = "mouseleave.tooltip",
27       placements = "top left bottom right".split(" "),
28       placement = d3.functor("top");
29
30     tooltip.title = function(_) {
31       if (arguments.length) {
32         title = d3.functor(_);
33         return tooltip;
34       } else {
35         return title;
36       }
37     };
38
39     tooltip.html = function(_) {
40       if (arguments.length) {
41         html = d3.functor(_);
42         return tooltip;
43       } else {
44         return html;
45       }
46     };
47
48     tooltip.placement = function(_) {
49       if (arguments.length) {
50         placement = d3.functor(_);
51         return tooltip;
52       } else {
53         return placement;
54       }
55     };
56
57     tooltip.show = function(selection) {
58       selection.each(show);
59     };
60
61     tooltip.hide = function(selection) {
62       selection.each(hide);
63     };
64
65     tooltip.toggle = function(selection) {
66       selection.each(toggle);
67     };
68
69     tooltip.destroy = function(selection) {
70       selection
71         .on(over, null)
72         .on(out, null)
73         .attr("title", function() {
74           return this.getAttribute("data-original-title") || this.getAttribute("title");
75         })
76         .attr("data-original-title", null)
77         .select(".tooltip")
78         .remove();
79     };
80
81     function setup() {
82       var root = d3.select(this),
83           animate = animation.apply(this, arguments),
84           tip = root.append("div")
85             .attr("class", "tooltip");
86
87       if (animate) {
88         tip.classed("fade", true);
89       }
90
91       // TODO "inside" checks?
92
93       tip.append("div")
94         .attr("class", "tooltip-arrow");
95       tip.append("div")
96         .attr("class", "tooltip-inner");
97
98       var place = placement.apply(this, arguments);
99       tip.classed(place, true);
100
101       root.on(over, show);
102       root.on(out, hide);
103     }
104
105     function show() {
106       var root = d3.select(this),
107           content = title.apply(this, arguments),
108           tip = root.select(".tooltip")
109             .classed("in", true),
110           markup = html.apply(this, arguments),
111           innercontent = tip.select(".tooltip-inner")[markup ? "html" : "text"](content),
112           place = placement.apply(this, arguments),
113           outer = getPosition(root.node()),
114           inner = getPosition(tip.node()),
115           pos;
116
117       switch (place) {
118         case "top":
119           pos = {x: outer.x + (outer.w - inner.w) / 2, y: outer.y - inner.h};
120           break;
121         case "right":
122           pos = {x: outer.x + outer.w, y: outer.y + (outer.h - inner.h) / 2};
123           break;
124         case "left":
125           pos = {x: outer.x - inner.w, y: outer.y + (outer.h - inner.h) / 2};
126           break;
127         case "bottom":
128           pos = {x: Math.max(0, outer.x + (outer.w - inner.w) / 2), y: outer.y + outer.h};
129           break;
130       }
131
132       tip.style(pos ?
133         {left: ~~pos.x + "px", top: ~~pos.y + "px"} :
134         {left: null, top: null});
135
136       this.tooltipVisible = true;
137     }
138
139     function hide() {
140       d3.select(this).select(".tooltip")
141         .classed("in", false);
142
143       this.tooltipVisible = false;
144     }
145
146     function toggle() {
147       if (this.tooltipVisible) {
148         hide.apply(this, arguments);
149       } else {
150         show.apply(this, arguments);
151       }
152     }
153
154     return tooltip;
155   };
156
157   function getPosition(node) {
158     var mode = d3.select(node).style('position');
159     if (mode === 'absolute' || mode === 'static') {
160       return {
161         x: node.offsetLeft,
162         y: node.offsetTop,
163         w: node.offsetWidth,
164         h: node.offsetHeight
165       };
166     } else {
167       return {
168         x: 0,
169         y: 0,
170         w: node.offsetWidth,
171         h: node.offsetHeight
172       };
173     }
174   }
175
176 })(this);
177 d3 = (function(){
178   var d3 = {version: "3.1.5"}; // semver
179 d3.ascending = function(a, b) {
180   return a < b ? -1 : a > b ? 1 : a >= b ? 0 : NaN;
181 };
182 d3.descending = function(a, b) {
183   return b < a ? -1 : b > a ? 1 : b >= a ? 0 : NaN;
184 };
185 d3.min = function(array, f) {
186   var i = -1,
187       n = array.length,
188       a,
189       b;
190   if (arguments.length === 1) {
191     while (++i < n && ((a = array[i]) == null || a != a)) a = undefined;
192     while (++i < n) if ((b = array[i]) != null && a > b) a = b;
193   } else {
194     while (++i < n && ((a = f.call(array, array[i], i)) == null || a != a)) a = undefined;
195     while (++i < n) if ((b = f.call(array, array[i], i)) != null && a > b) a = b;
196   }
197   return a;
198 };
199 d3.max = function(array, f) {
200   var i = -1,
201       n = array.length,
202       a,
203       b;
204   if (arguments.length === 1) {
205     while (++i < n && ((a = array[i]) == null || a != a)) a = undefined;
206     while (++i < n) if ((b = array[i]) != null && b > a) a = b;
207   } else {
208     while (++i < n && ((a = f.call(array, array[i], i)) == null || a != a)) a = undefined;
209     while (++i < n) if ((b = f.call(array, array[i], i)) != null && b > a) a = b;
210   }
211   return a;
212 };
213 d3.extent = function(array, f) {
214   var i = -1,
215       n = array.length,
216       a,
217       b,
218       c;
219   if (arguments.length === 1) {
220     while (++i < n && ((a = c = array[i]) == null || a != a)) a = c = undefined;
221     while (++i < n) if ((b = array[i]) != null) {
222       if (a > b) a = b;
223       if (c < b) c = b;
224     }
225   } else {
226     while (++i < n && ((a = c = f.call(array, array[i], i)) == null || a != a)) a = undefined;
227     while (++i < n) if ((b = f.call(array, array[i], i)) != null) {
228       if (a > b) a = b;
229       if (c < b) c = b;
230     }
231   }
232   return [a, c];
233 };
234 d3.sum = function(array, f) {
235   var s = 0,
236       n = array.length,
237       a,
238       i = -1;
239
240   if (arguments.length === 1) {
241     while (++i < n) if (!isNaN(a = +array[i])) s += a;
242   } else {
243     while (++i < n) if (!isNaN(a = +f.call(array, array[i], i))) s += a;
244   }
245
246   return s;
247 };
248 function d3_number(x) {
249   return x != null && !isNaN(x);
250 }
251
252 d3.mean = function(array, f) {
253   var n = array.length,
254       a,
255       m = 0,
256       i = -1,
257       j = 0;
258   if (arguments.length === 1) {
259     while (++i < n) if (d3_number(a = array[i])) m += (a - m) / ++j;
260   } else {
261     while (++i < n) if (d3_number(a = f.call(array, array[i], i))) m += (a - m) / ++j;
262   }
263   return j ? m : undefined;
264 };
265 // R-7 per <http://en.wikipedia.org/wiki/Quantile>
266 d3.quantile = function(values, p) {
267   var H = (values.length - 1) * p + 1,
268       h = Math.floor(H),
269       v = +values[h - 1],
270       e = H - h;
271   return e ? v + e * (values[h] - v) : v;
272 };
273
274 d3.median = function(array, f) {
275   if (arguments.length > 1) array = array.map(f);
276   array = array.filter(d3_number);
277   return array.length ? d3.quantile(array.sort(d3.ascending), .5) : undefined;
278 };
279 d3.bisector = function(f) {
280   return {
281     left: function(a, x, lo, hi) {
282       if (arguments.length < 3) lo = 0;
283       if (arguments.length < 4) hi = a.length;
284       while (lo < hi) {
285         var mid = lo + hi >>> 1;
286         if (f.call(a, a[mid], mid) < x) lo = mid + 1;
287         else hi = mid;
288       }
289       return lo;
290     },
291     right: function(a, x, lo, hi) {
292       if (arguments.length < 3) lo = 0;
293       if (arguments.length < 4) hi = a.length;
294       while (lo < hi) {
295         var mid = lo + hi >>> 1;
296         if (x < f.call(a, a[mid], mid)) hi = mid;
297         else lo = mid + 1;
298       }
299       return lo;
300     }
301   };
302 };
303
304 var d3_bisector = d3.bisector(function(d) { return d; });
305 d3.bisectLeft = d3_bisector.left;
306 d3.bisect = d3.bisectRight = d3_bisector.right;
307 d3.shuffle = function(array) {
308   var m = array.length, t, i;
309   while (m) {
310     i = Math.random() * m-- | 0;
311     t = array[m], array[m] = array[i], array[i] = t;
312   }
313   return array;
314 };
315 d3.permute = function(array, indexes) {
316   var permutes = [],
317       i = -1,
318       n = indexes.length;
319   while (++i < n) permutes[i] = array[indexes[i]];
320   return permutes;
321 };
322
323 d3.zip = function() {
324   if (!(n = arguments.length)) return [];
325   for (var i = -1, m = d3.min(arguments, d3_zipLength), zips = new Array(m); ++i < m;) {
326     for (var j = -1, n, zip = zips[i] = new Array(n); ++j < n;) {
327       zip[j] = arguments[j][i];
328     }
329   }
330   return zips;
331 };
332
333 function d3_zipLength(d) {
334   return d.length;
335 }
336
337 d3.transpose = function(matrix) {
338   return d3.zip.apply(d3, matrix);
339 };
340 d3.keys = function(map) {
341   var keys = [];
342   for (var key in map) keys.push(key);
343   return keys;
344 };
345 d3.values = function(map) {
346   var values = [];
347   for (var key in map) values.push(map[key]);
348   return values;
349 };
350 d3.entries = function(map) {
351   var entries = [];
352   for (var key in map) entries.push({key: key, value: map[key]});
353   return entries;
354 };
355 d3.merge = function(arrays) {
356   return Array.prototype.concat.apply([], arrays);
357 };
358 d3.range = function(start, stop, step) {
359   if (arguments.length < 3) {
360     step = 1;
361     if (arguments.length < 2) {
362       stop = start;
363       start = 0;
364     }
365   }
366   if ((stop - start) / step === Infinity) throw new Error("infinite range");
367   var range = [],
368        k = d3_range_integerScale(Math.abs(step)),
369        i = -1,
370        j;
371   start *= k, stop *= k, step *= k;
372   if (step < 0) while ((j = start + step * ++i) > stop) range.push(j / k);
373   else while ((j = start + step * ++i) < stop) range.push(j / k);
374   return range;
375 };
376
377 function d3_range_integerScale(x) {
378   var k = 1;
379   while (x * k % 1) k *= 10;
380   return k;
381 }
382 function d3_class(ctor, properties) {
383   try {
384     for (var key in properties) {
385       Object.defineProperty(ctor.prototype, key, {
386         value: properties[key],
387         enumerable: false
388       });
389     }
390   } catch (e) {
391     ctor.prototype = properties;
392   }
393 }
394
395 d3.map = function(object) {
396   var map = new d3_Map;
397   for (var key in object) map.set(key, object[key]);
398   return map;
399 };
400
401 function d3_Map() {}
402
403 d3_class(d3_Map, {
404   has: function(key) {
405     return d3_map_prefix + key in this;
406   },
407   get: function(key) {
408     return this[d3_map_prefix + key];
409   },
410   set: function(key, value) {
411     return this[d3_map_prefix + key] = value;
412   },
413   remove: function(key) {
414     key = d3_map_prefix + key;
415     return key in this && delete this[key];
416   },
417   keys: function() {
418     var keys = [];
419     this.forEach(function(key) { keys.push(key); });
420     return keys;
421   },
422   values: function() {
423     var values = [];
424     this.forEach(function(key, value) { values.push(value); });
425     return values;
426   },
427   entries: function() {
428     var entries = [];
429     this.forEach(function(key, value) { entries.push({key: key, value: value}); });
430     return entries;
431   },
432   forEach: function(f) {
433     for (var key in this) {
434       if (key.charCodeAt(0) === d3_map_prefixCode) {
435         f.call(this, key.substring(1), this[key]);
436       }
437     }
438   }
439 });
440
441 var d3_map_prefix = "\0", // prevent collision with built-ins
442     d3_map_prefixCode = d3_map_prefix.charCodeAt(0);
443
444 d3.nest = function() {
445   var nest = {},
446       keys = [],
447       sortKeys = [],
448       sortValues,
449       rollup;
450
451   function map(mapType, array, depth) {
452     if (depth >= keys.length) return rollup
453         ? rollup.call(nest, array) : (sortValues
454         ? array.sort(sortValues)
455         : array);
456
457     var i = -1,
458         n = array.length,
459         key = keys[depth++],
460         keyValue,
461         object,
462         setter,
463         valuesByKey = new d3_Map,
464         values;
465
466     while (++i < n) {
467       if (values = valuesByKey.get(keyValue = key(object = array[i]))) {
468         values.push(object);
469       } else {
470         valuesByKey.set(keyValue, [object]);
471       }
472     }
473
474     if (mapType) {
475       object = mapType();
476       setter = function(keyValue, values) {
477         object.set(keyValue, map(mapType, values, depth));
478       };
479     } else {
480       object = {};
481       setter = function(keyValue, values) {
482         object[keyValue] = map(mapType, values, depth);
483       };
484     }
485
486     valuesByKey.forEach(setter);
487     return object;
488   }
489
490   function entries(map, depth) {
491     if (depth >= keys.length) return map;
492
493     var array = [],
494         sortKey = sortKeys[depth++];
495
496     map.forEach(function(key, keyMap) {
497       array.push({key: key, values: entries(keyMap, depth)});
498     });
499
500     return sortKey
501         ? array.sort(function(a, b) { return sortKey(a.key, b.key); })
502         : array;
503   }
504
505   nest.map = function(array, mapType) {
506     return map(mapType, array, 0);
507   };
508
509   nest.entries = function(array) {
510     return entries(map(d3.map, array, 0), 0);
511   };
512
513   nest.key = function(d) {
514     keys.push(d);
515     return nest;
516   };
517
518   // Specifies the order for the most-recently specified key.
519   // Note: only applies to entries. Map keys are unordered!
520   nest.sortKeys = function(order) {
521     sortKeys[keys.length - 1] = order;
522     return nest;
523   };
524
525   // Specifies the order for leaf values.
526   // Applies to both maps and entries array.
527   nest.sortValues = function(order) {
528     sortValues = order;
529     return nest;
530   };
531
532   nest.rollup = function(f) {
533     rollup = f;
534     return nest;
535   };
536
537   return nest;
538 };
539
540 d3.set = function(array) {
541   var set = new d3_Set();
542   if (array) for (var i = 0; i < array.length; i++) set.add(array[i]);
543   return set;
544 };
545
546 function d3_Set() {}
547
548 d3_class(d3_Set, {
549   has: function(value) {
550     return d3_map_prefix + value in this;
551   },
552   add: function(value) {
553     this[d3_map_prefix + value] = true;
554     return value;
555   },
556   remove: function(value) {
557     value = d3_map_prefix + value;
558     return value in this && delete this[value];
559   },
560   values: function() {
561     var values = [];
562     this.forEach(function(value) {
563       values.push(value);
564     });
565     return values;
566   },
567   forEach: function(f) {
568     for (var value in this) {
569       if (value.charCodeAt(0) === d3_map_prefixCode) {
570         f.call(this, value.substring(1));
571       }
572     }
573   }
574 });
575 d3.behavior = {};
576 var d3_document = document,
577     d3_window = window;
578 // Copies a variable number of methods from source to target.
579 d3.rebind = function(target, source) {
580   var i = 1, n = arguments.length, method;
581   while (++i < n) target[method = arguments[i]] = d3_rebind(target, source, source[method]);
582   return target;
583 };
584
585 // Method is assumed to be a standard D3 getter-setter:
586 // If passed with no arguments, gets the value.
587 // If passed with arguments, sets the value and returns the target.
588 function d3_rebind(target, source, method) {
589   return function() {
590     var value = method.apply(source, arguments);
591     return value === source ? target : value;
592   };
593 }
594
595 d3.dispatch = function() {
596   var dispatch = new d3_dispatch,
597       i = -1,
598       n = arguments.length;
599   while (++i < n) dispatch[arguments[i]] = d3_dispatch_event(dispatch);
600   return dispatch;
601 };
602
603 function d3_dispatch() {}
604
605 d3_dispatch.prototype.on = function(type, listener) {
606   var i = type.indexOf("."),
607       name = "";
608
609   // Extract optional namespace, e.g., "click.foo"
610   if (i >= 0) {
611     name = type.substring(i + 1);
612     type = type.substring(0, i);
613   }
614
615   if (type) return arguments.length < 2
616       ? this[type].on(name)
617       : this[type].on(name, listener);
618
619   if (arguments.length === 2) {
620     if (listener == null) for (type in this) {
621       if (this.hasOwnProperty(type)) this[type].on(name, null);
622     }
623     return this;
624   }
625 };
626
627 function d3_dispatch_event(dispatch) {
628   var listeners = [],
629       listenerByName = new d3_Map;
630
631   function event() {
632     var z = listeners, // defensive reference
633         i = -1,
634         n = z.length,
635         l;
636     while (++i < n) if (l = z[i].on) l.apply(this, arguments);
637     return dispatch;
638   }
639
640   event.on = function(name, listener) {
641     var l = listenerByName.get(name),
642         i;
643
644     // return the current listener, if any
645     if (arguments.length < 2) return l && l.on;
646
647     // remove the old listener, if any (with copy-on-write)
648     if (l) {
649       l.on = null;
650       listeners = listeners.slice(0, i = listeners.indexOf(l)).concat(listeners.slice(i + 1));
651       listenerByName.remove(name);
652     }
653
654     // add the new listener, if any
655     if (listener) listeners.push(listenerByName.set(name, {on: listener}));
656
657     return dispatch;
658   };
659
660   return event;
661 }
662
663 d3.event = null;
664
665 function d3_eventCancel() {
666   d3.event.stopPropagation();
667   d3.event.preventDefault();
668 }
669
670 function d3_eventSource() {
671   var e = d3.event, s;
672   while (s = e.sourceEvent) e = s;
673   return e;
674 }
675
676 // Registers an event listener for the specified target that cancels the next
677 // event for the specified type, but only if it occurs immediately. This is
678 // useful to disambiguate dragging from clicking.
679 function d3_eventSuppress(target, type) {
680   function off() { target.on(type, null); }
681   target.on(type, function() { d3_eventCancel(); off(); }, true);
682   setTimeout(off, 0); // clear the handler if it doesn't fire
683 }
684
685 // Like d3.dispatch, but for custom events abstracting native UI events. These
686 // events have a target component (such as a brush), a target element (such as
687 // the svg:g element containing the brush) and the standard arguments `d` (the
688 // target element's data) and `i` (the selection index of the target element).
689 function d3_eventDispatch(target) {
690   var dispatch = new d3_dispatch,
691       i = 0,
692       n = arguments.length;
693
694   while (++i < n) dispatch[arguments[i]] = d3_dispatch_event(dispatch);
695
696   // Creates a dispatch context for the specified `thiz` (typically, the target
697   // DOM element that received the source event) and `argumentz` (typically, the
698   // data `d` and index `i` of the target element). The returned function can be
699   // used to dispatch an event to any registered listeners; the function takes a
700   // single argument as input, being the event to dispatch. The event must have
701   // a "type" attribute which corresponds to a type registered in the
702   // constructor. This context will automatically populate the "sourceEvent" and
703   // "target" attributes of the event, as well as setting the `d3.event` global
704   // for the duration of the notification.
705   dispatch.of = function(thiz, argumentz) {
706     return function(e1) {
707       try {
708         var e0 =
709         e1.sourceEvent = d3.event;
710         e1.target = target;
711         d3.event = e1;
712         dispatch[e1.type].apply(thiz, argumentz);
713       } finally {
714         d3.event = e0;
715       }
716     };
717   };
718
719   return dispatch;
720 }
721
722 d3.mouse = function(container) {
723   return d3_mousePoint(container, d3_eventSource());
724 };
725
726 // https://bugs.webkit.org/show_bug.cgi?id=44083
727 var d3_mouse_bug44083 = /WebKit/.test(d3_window.navigator.userAgent) ? -1 : 0;
728
729 function d3_mousePoint(container, e) {
730   var svg = container.ownerSVGElement || container;
731   if (svg.createSVGPoint) {
732     var point = svg.createSVGPoint();
733     if (d3_mouse_bug44083 < 0 && (d3_window.scrollX || d3_window.scrollY)) {
734       svg = d3.select(d3_document.body).append("svg")
735           .style("position", "absolute")
736           .style("top", 0)
737           .style("left", 0);
738       var ctm = svg[0][0].getScreenCTM();
739       d3_mouse_bug44083 = !(ctm.f || ctm.e);
740       svg.remove();
741     }
742     if (d3_mouse_bug44083) {
743       point.x = e.pageX;
744       point.y = e.pageY;
745     } else {
746       point.x = e.clientX;
747       point.y = e.clientY;
748     }
749     point = point.matrixTransform(container.getScreenCTM().inverse());
750     return [point.x, point.y];
751   }
752   var rect = container.getBoundingClientRect();
753   return [e.clientX - rect.left - container.clientLeft, e.clientY - rect.top - container.clientTop];
754 };
755
756 var d3_array = d3_arraySlice; // conversion for NodeLists
757
758 function d3_arrayCopy(pseudoarray) {
759   var i = -1, n = pseudoarray.length, array = [];
760   while (++i < n) array.push(pseudoarray[i]);
761   return array;
762 }
763
764 function d3_arraySlice(pseudoarray) {
765   return Array.prototype.slice.call(pseudoarray);
766 }
767
768 try {
769   d3_array(d3_document.documentElement.childNodes)[0].nodeType;
770 } catch(e) {
771   d3_array = d3_arrayCopy;
772 }
773
774 var d3_arraySubclass = [].__proto__?
775
776 // Until ECMAScript supports array subclassing, prototype injection works well.
777 function(array, prototype) {
778   array.__proto__ = prototype;
779 }:
780
781 // And if your browser doesn't support __proto__, we'll use direct extension.
782 function(array, prototype) {
783   for (var property in prototype) array[property] = prototype[property];
784 };
785
786 d3.touches = function(container, touches) {
787   if (arguments.length < 2) touches = d3_eventSource().touches;
788   return touches ? d3_array(touches).map(function(touch) {
789     var point = d3_mousePoint(container, touch);
790     point.identifier = touch.identifier;
791     return point;
792   }) : [];
793 };
794
795 function d3_selection(groups) {
796   d3_arraySubclass(groups, d3_selectionPrototype);
797   return groups;
798 }
799
800 var d3_select = function(s, n) { return n.querySelector(s); },
801     d3_selectAll = function(s, n) { return n.querySelectorAll(s); },
802     d3_selectRoot = d3_document.documentElement,
803     d3_selectMatcher = d3_selectRoot.matchesSelector || d3_selectRoot.webkitMatchesSelector || d3_selectRoot.mozMatchesSelector || d3_selectRoot.msMatchesSelector || d3_selectRoot.oMatchesSelector,
804     d3_selectMatches = function(n, s) { return d3_selectMatcher.call(n, s); };
805
806 // Prefer Sizzle, if available.
807 if (typeof Sizzle === "function") {
808   d3_select = function(s, n) { return Sizzle(s, n)[0] || null; };
809   d3_selectAll = function(s, n) { return Sizzle.uniqueSort(Sizzle(s, n)); };
810   d3_selectMatches = Sizzle.matchesSelector;
811 }
812
813 var d3_selectionPrototype = [];
814
815 d3.selection = function() {
816   return d3_selectionRoot;
817 };
818
819 d3.selection.prototype = d3_selectionPrototype;
820
821
822 d3_selectionPrototype.select = function(selector) {
823   var subgroups = [],
824       subgroup,
825       subnode,
826       group,
827       node;
828
829   if (typeof selector !== "function") selector = d3_selection_selector(selector);
830
831   for (var j = -1, m = this.length; ++j < m;) {
832     subgroups.push(subgroup = []);
833     subgroup.parentNode = (group = this[j]).parentNode;
834     for (var i = -1, n = group.length; ++i < n;) {
835       if (node = group[i]) {
836         subgroup.push(subnode = selector.call(node, node.__data__, i));
837         if (subnode && "__data__" in node) subnode.__data__ = node.__data__;
838       } else {
839         subgroup.push(null);
840       }
841     }
842   }
843
844   return d3_selection(subgroups);
845 };
846
847 function d3_selection_selector(selector) {
848   return function() {
849     return d3_select(selector, this);
850   };
851 }
852
853 d3_selectionPrototype.selectAll = function(selector) {
854   var subgroups = [],
855       subgroup,
856       node;
857
858   if (typeof selector !== "function") selector = d3_selection_selectorAll(selector);
859
860   for (var j = -1, m = this.length; ++j < m;) {
861     for (var group = this[j], i = -1, n = group.length; ++i < n;) {
862       if (node = group[i]) {
863         subgroups.push(subgroup = d3_array(selector.call(node, node.__data__, i)));
864         subgroup.parentNode = node;
865       }
866     }
867   }
868
869   return d3_selection(subgroups);
870 };
871
872 function d3_selection_selectorAll(selector) {
873   return function() {
874     return d3_selectAll(selector, this);
875   };
876 }
877 var d3_nsPrefix = {
878   svg: "http://www.w3.org/2000/svg",
879   xhtml: "http://www.w3.org/1999/xhtml",
880   xlink: "http://www.w3.org/1999/xlink",
881   xml: "http://www.w3.org/XML/1998/namespace",
882   xmlns: "http://www.w3.org/2000/xmlns/"
883 };
884
885 d3.ns = {
886   prefix: d3_nsPrefix,
887   qualify: function(name) {
888     var i = name.indexOf(":"),
889         prefix = name;
890     if (i >= 0) {
891       prefix = name.substring(0, i);
892       name = name.substring(i + 1);
893     }
894     return d3_nsPrefix.hasOwnProperty(prefix)
895         ? {space: d3_nsPrefix[prefix], local: name}
896         : name;
897   }
898 };
899
900 d3_selectionPrototype.attr = function(name, value) {
901   if (arguments.length < 2) {
902
903     // For attr(string), return the attribute value for the first node.
904     if (typeof name === "string") {
905       var node = this.node();
906       name = d3.ns.qualify(name);
907       return name.local
908           ? node.getAttributeNS(name.space, name.local)
909           : node.getAttribute(name);
910     }
911
912     // For attr(object), the object specifies the names and values of the
913     // attributes to set or remove. The values may be functions that are
914     // evaluated for each element.
915     for (value in name) this.each(d3_selection_attr(value, name[value]));
916     return this;
917   }
918
919   return this.each(d3_selection_attr(name, value));
920 };
921
922 function d3_selection_attr(name, value) {
923   name = d3.ns.qualify(name);
924
925   // For attr(string, null), remove the attribute with the specified name.
926   function attrNull() {
927     this.removeAttribute(name);
928   }
929   function attrNullNS() {
930     this.removeAttributeNS(name.space, name.local);
931   }
932
933   // For attr(string, string), set the attribute with the specified name.
934   function attrConstant() {
935     this.setAttribute(name, value);
936   }
937   function attrConstantNS() {
938     this.setAttributeNS(name.space, name.local, value);
939   }
940
941   // For attr(string, function), evaluate the function for each element, and set
942   // or remove the attribute as appropriate.
943   function attrFunction() {
944     var x = value.apply(this, arguments);
945     if (x == null) this.removeAttribute(name);
946     else this.setAttribute(name, x);
947   }
948   function attrFunctionNS() {
949     var x = value.apply(this, arguments);
950     if (x == null) this.removeAttributeNS(name.space, name.local);
951     else this.setAttributeNS(name.space, name.local, x);
952   }
953
954   return value == null
955       ? (name.local ? attrNullNS : attrNull) : (typeof value === "function"
956       ? (name.local ? attrFunctionNS : attrFunction)
957       : (name.local ? attrConstantNS : attrConstant));
958 }
959 function d3_collapse(s) {
960   return s.trim().replace(/\s+/g, " ");
961 }
962 d3.requote = function(s) {
963   return s.replace(d3_requote_re, "\\$&");
964 };
965
966 var d3_requote_re = /[\\\^\$\*\+\?\|\[\]\(\)\.\{\}]/g;
967
968 d3_selectionPrototype.classed = function(name, value) {
969   if (arguments.length < 2) {
970
971     // For classed(string), return true only if the first node has the specified
972     // class or classes. Note that even if the browser supports DOMTokenList, it
973     // probably doesn't support it on SVG elements (which can be animated).
974     if (typeof name === "string") {
975       var node = this.node(),
976           n = (name = name.trim().split(/^|\s+/g)).length,
977           i = -1;
978       if (value = node.classList) {
979         while (++i < n) if (!value.contains(name[i])) return false;
980       } else {
981         value = node.getAttribute("class");
982         while (++i < n) if (!d3_selection_classedRe(name[i]).test(value)) return false;
983       }
984       return true;
985     }
986
987     // For classed(object), the object specifies the names of classes to add or
988     // remove. The values may be functions that are evaluated for each element.
989     for (value in name) this.each(d3_selection_classed(value, name[value]));
990     return this;
991   }
992
993   // Otherwise, both a name and a value are specified, and are handled as below.
994   return this.each(d3_selection_classed(name, value));
995 };
996
997 function d3_selection_classedRe(name) {
998   return new RegExp("(?:^|\\s+)" + d3.requote(name) + "(?:\\s+|$)", "g");
999 }
1000
1001 // Multiple class names are allowed (e.g., "foo bar").
1002 function d3_selection_classed(name, value) {
1003   name = name.trim().split(/\s+/).map(d3_selection_classedName);
1004   var n = name.length;
1005
1006   function classedConstant() {
1007     var i = -1;
1008     while (++i < n) name[i](this, value);
1009   }
1010
1011   // When the value is a function, the function is still evaluated only once per
1012   // element even if there are multiple class names.
1013   function classedFunction() {
1014     var i = -1, x = value.apply(this, arguments);
1015     while (++i < n) name[i](this, x);
1016   }
1017
1018   return typeof value === "function"
1019       ? classedFunction
1020       : classedConstant;
1021 }
1022
1023 function d3_selection_classedName(name) {
1024   var re = d3_selection_classedRe(name);
1025   return function(node, value) {
1026     if (c = node.classList) return value ? c.add(name) : c.remove(name);
1027     var c = node.getAttribute("class") || "";
1028     if (value) {
1029       re.lastIndex = 0;
1030       if (!re.test(c)) node.setAttribute("class", d3_collapse(c + " " + name));
1031     } else {
1032       node.setAttribute("class", d3_collapse(c.replace(re, " ")));
1033     }
1034   };
1035 }
1036
1037 d3_selectionPrototype.style = function(name, value, priority) {
1038   var n = arguments.length;
1039   if (n < 3) {
1040
1041     // For style(object) or style(object, string), the object specifies the
1042     // names and values of the attributes to set or remove. The values may be
1043     // functions that are evaluated for each element. The optional string
1044     // specifies the priority.
1045     if (typeof name !== "string") {
1046       if (n < 2) value = "";
1047       for (priority in name) this.each(d3_selection_style(priority, name[priority], value));
1048       return this;
1049     }
1050
1051     // For style(string), return the computed style value for the first node.
1052     if (n < 2) return d3_window.getComputedStyle(this.node(), null).getPropertyValue(name);
1053
1054     // For style(string, string) or style(string, function), use the default
1055     // priority. The priority is ignored for style(string, null).
1056     priority = "";
1057   }
1058
1059   // Otherwise, a name, value and priority are specified, and handled as below.
1060   return this.each(d3_selection_style(name, value, priority));
1061 };
1062
1063 function d3_selection_style(name, value, priority) {
1064
1065   // For style(name, null) or style(name, null, priority), remove the style
1066   // property with the specified name. The priority is ignored.
1067   function styleNull() {
1068     this.style.removeProperty(name);
1069   }
1070
1071   // For style(name, string) or style(name, string, priority), set the style
1072   // property with the specified name, using the specified priority.
1073   function styleConstant() {
1074     this.style.setProperty(name, value, priority);
1075   }
1076
1077   // For style(name, function) or style(name, function, priority), evaluate the
1078   // function for each element, and set or remove the style property as
1079   // appropriate. When setting, use the specified priority.
1080   function styleFunction() {
1081     var x = value.apply(this, arguments);
1082     if (x == null) this.style.removeProperty(name);
1083     else this.style.setProperty(name, x, priority);
1084   }
1085
1086   return value == null
1087       ? styleNull : (typeof value === "function"
1088       ? styleFunction : styleConstant);
1089 }
1090
1091 d3_selectionPrototype.property = function(name, value) {
1092   if (arguments.length < 2) {
1093
1094     // For property(string), return the property value for the first node.
1095     if (typeof name === "string") return this.node()[name];
1096
1097     // For property(object), the object specifies the names and values of the
1098     // properties to set or remove. The values may be functions that are
1099     // evaluated for each element.
1100     for (value in name) this.each(d3_selection_property(value, name[value]));
1101     return this;
1102   }
1103
1104   // Otherwise, both a name and a value are specified, and are handled as below.
1105   return this.each(d3_selection_property(name, value));
1106 };
1107
1108 function d3_selection_property(name, value) {
1109
1110   // For property(name, null), remove the property with the specified name.
1111   function propertyNull() {
1112     delete this[name];
1113   }
1114
1115   // For property(name, string), set the property with the specified name.
1116   function propertyConstant() {
1117     this[name] = value;
1118   }
1119
1120   // For property(name, function), evaluate the function for each element, and
1121   // set or remove the property as appropriate.
1122   function propertyFunction() {
1123     var x = value.apply(this, arguments);
1124     if (x == null) delete this[name];
1125     else this[name] = x;
1126   }
1127
1128   return value == null
1129       ? propertyNull : (typeof value === "function"
1130       ? propertyFunction : propertyConstant);
1131 }
1132
1133 d3_selectionPrototype.text = function(value) {
1134   return arguments.length
1135       ? this.each(typeof value === "function"
1136       ? function() { var v = value.apply(this, arguments); this.textContent = v == null ? "" : v; } : value == null
1137       ? function() { this.textContent = ""; }
1138       : function() { this.textContent = value; })
1139       : this.node().textContent;
1140 };
1141
1142 d3_selectionPrototype.html = function(value) {
1143   return arguments.length
1144       ? this.each(typeof value === "function"
1145       ? function() { var v = value.apply(this, arguments); this.innerHTML = v == null ? "" : v; } : value == null
1146       ? function() { this.innerHTML = ""; }
1147       : function() { this.innerHTML = value; })
1148       : this.node().innerHTML;
1149 };
1150
1151 // TODO append(node)?
1152 // TODO append(function)?
1153 d3_selectionPrototype.append = function(name) {
1154   name = d3.ns.qualify(name);
1155
1156   function append() {
1157     return this.appendChild(d3_document.createElementNS(this.namespaceURI, name));
1158   }
1159
1160   function appendNS() {
1161     return this.appendChild(d3_document.createElementNS(name.space, name.local));
1162   }
1163
1164   return this.select(name.local ? appendNS : append);
1165 };
1166
1167 d3_selectionPrototype.insert = function(name, before) {
1168   name = d3.ns.qualify(name);
1169
1170   if (typeof before !== "function") before = d3_selection_selector(before);
1171
1172   function insert(d, i) {
1173     return this.insertBefore(
1174         d3_document.createElementNS(this.namespaceURI, name),
1175         before.call(this, d, i));
1176   }
1177
1178   function insertNS(d, i) {
1179     return this.insertBefore(
1180         d3_document.createElementNS(name.space, name.local),
1181         before.call(this, d, i));
1182   }
1183
1184   return this.select(name.local ? insertNS : insert);
1185 };
1186
1187 // TODO remove(selector)?
1188 // TODO remove(node)?
1189 // TODO remove(function)?
1190 d3_selectionPrototype.remove = function() {
1191   return this.each(function() {
1192     var parent = this.parentNode;
1193     if (parent) parent.removeChild(this);
1194   });
1195 };
1196
1197 d3_selectionPrototype.data = function(value, key) {
1198   var i = -1,
1199       n = this.length,
1200       group,
1201       node;
1202
1203   // If no value is specified, return the first value.
1204   if (!arguments.length) {
1205     value = new Array(n = (group = this[0]).length);
1206     while (++i < n) {
1207       if (node = group[i]) {
1208         value[i] = node.__data__;
1209       }
1210     }
1211     return value;
1212   }
1213
1214   function bind(group, groupData) {
1215     var i,
1216         n = group.length,
1217         m = groupData.length,
1218         n0 = Math.min(n, m),
1219         updateNodes = new Array(m),
1220         enterNodes = new Array(m),
1221         exitNodes = new Array(n),
1222         node,
1223         nodeData;
1224
1225     if (key) {
1226       var nodeByKeyValue = new d3_Map,
1227           dataByKeyValue = new d3_Map,
1228           keyValues = [],
1229           keyValue;
1230
1231       for (i = -1; ++i < n;) {
1232         keyValue = key.call(node = group[i], node.__data__, i);
1233         if (nodeByKeyValue.has(keyValue)) {
1234           exitNodes[i] = node; // duplicate selection key
1235         } else {
1236           nodeByKeyValue.set(keyValue, node);
1237         }
1238         keyValues.push(keyValue);
1239       }
1240
1241       for (i = -1; ++i < m;) {
1242         keyValue = key.call(groupData, nodeData = groupData[i], i);
1243         if (node = nodeByKeyValue.get(keyValue)) {
1244           updateNodes[i] = node;
1245           node.__data__ = nodeData;
1246         } else if (!dataByKeyValue.has(keyValue)) { // no duplicate data key
1247           enterNodes[i] = d3_selection_dataNode(nodeData);
1248         }
1249         dataByKeyValue.set(keyValue, nodeData);
1250         nodeByKeyValue.remove(keyValue);
1251       }
1252
1253       for (i = -1; ++i < n;) {
1254         if (nodeByKeyValue.has(keyValues[i])) {
1255           exitNodes[i] = group[i];
1256         }
1257       }
1258     } else {
1259       for (i = -1; ++i < n0;) {
1260         node = group[i];
1261         nodeData = groupData[i];
1262         if (node) {
1263           node.__data__ = nodeData;
1264           updateNodes[i] = node;
1265         } else {
1266           enterNodes[i] = d3_selection_dataNode(nodeData);
1267         }
1268       }
1269       for (; i < m; ++i) {
1270         enterNodes[i] = d3_selection_dataNode(groupData[i]);
1271       }
1272       for (; i < n; ++i) {
1273         exitNodes[i] = group[i];
1274       }
1275     }
1276
1277     enterNodes.update
1278         = updateNodes;
1279
1280     enterNodes.parentNode
1281         = updateNodes.parentNode
1282         = exitNodes.parentNode
1283         = group.parentNode;
1284
1285     enter.push(enterNodes);
1286     update.push(updateNodes);
1287     exit.push(exitNodes);
1288   }
1289
1290   var enter = d3_selection_enter([]),
1291       update = d3_selection([]),
1292       exit = d3_selection([]);
1293
1294   if (typeof value === "function") {
1295     while (++i < n) {
1296       bind(group = this[i], value.call(group, group.parentNode.__data__, i));
1297     }
1298   } else {
1299     while (++i < n) {
1300       bind(group = this[i], value);
1301     }
1302   }
1303
1304   update.enter = function() { return enter; };
1305   update.exit = function() { return exit; };
1306   return update;
1307 };
1308
1309 function d3_selection_dataNode(data) {
1310   return {__data__: data};
1311 }
1312
1313 d3_selectionPrototype.datum = function(value) {
1314   return arguments.length
1315       ? this.property("__data__", value)
1316       : this.property("__data__");
1317 };
1318
1319 d3_selectionPrototype.filter = function(filter) {
1320   var subgroups = [],
1321       subgroup,
1322       group,
1323       node;
1324
1325   if (typeof filter !== "function") filter = d3_selection_filter(filter);
1326
1327   for (var j = 0, m = this.length; j < m; j++) {
1328     subgroups.push(subgroup = []);
1329     subgroup.parentNode = (group = this[j]).parentNode;
1330     for (var i = 0, n = group.length; i < n; i++) {
1331       if ((node = group[i]) && filter.call(node, node.__data__, i)) {
1332         subgroup.push(node);
1333       }
1334     }
1335   }
1336
1337   return d3_selection(subgroups);
1338 };
1339
1340 function d3_selection_filter(selector) {
1341   return function() {
1342     return d3_selectMatches(this, selector);
1343   };
1344 }
1345
1346 d3_selectionPrototype.order = function() {
1347   for (var j = -1, m = this.length; ++j < m;) {
1348     for (var group = this[j], i = group.length - 1, next = group[i], node; --i >= 0;) {
1349       if (node = group[i]) {
1350         if (next && next !== node.nextSibling) next.parentNode.insertBefore(node, next);
1351         next = node;
1352       }
1353     }
1354   }
1355   return this;
1356 };
1357
1358 d3_selectionPrototype.sort = function(comparator) {
1359   comparator = d3_selection_sortComparator.apply(this, arguments);
1360   for (var j = -1, m = this.length; ++j < m;) this[j].sort(comparator);
1361   return this.order();
1362 };
1363
1364 function d3_selection_sortComparator(comparator) {
1365   if (!arguments.length) comparator = d3.ascending;
1366   return function(a, b) {
1367     return (!a - !b) || comparator(a.__data__, b.__data__);
1368   };
1369 }
1370 function d3_noop() {}
1371
1372 d3_selectionPrototype.on = function(type, listener, capture) {
1373   var n = arguments.length;
1374   if (n < 3) {
1375
1376     // For on(object) or on(object, boolean), the object specifies the event
1377     // types and listeners to add or remove. The optional boolean specifies
1378     // whether the listener captures events.
1379     if (typeof type !== "string") {
1380       if (n < 2) listener = false;
1381       for (capture in type) this.each(d3_selection_on(capture, type[capture], listener));
1382       return this;
1383     }
1384
1385     // For on(string), return the listener for the first node.
1386     if (n < 2) return (n = this.node()["__on" + type]) && n._;
1387
1388     // For on(string, function), use the default capture.
1389     capture = false;
1390   }
1391
1392   // Otherwise, a type, listener and capture are specified, and handled as below.
1393   return this.each(d3_selection_on(type, listener, capture));
1394 };
1395
1396 function d3_selection_on(type, listener, capture) {
1397   var name = "__on" + type,
1398       i = type.indexOf("."),
1399       wrap = d3_selection_onListener;
1400
1401   if (i > 0) type = type.substring(0, i);
1402   var filter = d3_selection_onFilters.get(type);
1403   if (filter) type = filter, wrap = d3_selection_onFilter;
1404
1405   function onRemove() {
1406     var l = this[name];
1407     if (l) {
1408       this.removeEventListener(type, l, l.$);
1409       delete this[name];
1410     }
1411   }
1412
1413   function onAdd() {
1414     var l = wrap(listener, d3_array(arguments));
1415     if (typeof Raven !== 'undefined') l = Raven.wrap(l);
1416     onRemove.call(this);
1417     this.addEventListener(type, this[name] = l, l.$ = capture);
1418     l._ = listener;
1419   }
1420
1421   function removeAll() {
1422     var re = new RegExp("^__on([^.]+)" + d3.requote(type) + "$"),
1423         match;
1424     for (var name in this) {
1425       if (match = name.match(re)) {
1426         var l = this[name];
1427         this.removeEventListener(match[1], l, l.$);
1428         delete this[name];
1429       }
1430     }
1431   }
1432
1433   return i
1434       ? listener ? onAdd : onRemove
1435       : listener ? d3_noop : removeAll;
1436 }
1437
1438 var d3_selection_onFilters = d3.map({
1439   mouseenter: "mouseover",
1440   mouseleave: "mouseout"
1441 });
1442
1443 d3_selection_onFilters.forEach(function(k) {
1444   if ("on" + k in d3_document) d3_selection_onFilters.remove(k);
1445 });
1446
1447 function d3_selection_onListener(listener, argumentz) {
1448   return function(e) {
1449     var o = d3.event; // Events can be reentrant (e.g., focus).
1450     d3.event = e;
1451     argumentz[0] = this.__data__;
1452     try {
1453       listener.apply(this, argumentz);
1454     } finally {
1455       d3.event = o;
1456     }
1457   };
1458 }
1459
1460 function d3_selection_onFilter(listener, argumentz) {
1461   var l = d3_selection_onListener(listener, argumentz);
1462   return function(e) {
1463     var target = this, related = e.relatedTarget;
1464     if (!related || (related !== target && !(related.compareDocumentPosition(target) & 8))) {
1465       l.call(target, e);
1466     }
1467   };
1468 }
1469
1470 d3_selectionPrototype.each = function(callback) {
1471   return d3_selection_each(this, function(node, i, j) {
1472     callback.call(node, node.__data__, i, j);
1473   });
1474 };
1475
1476 function d3_selection_each(groups, callback) {
1477   for (var j = 0, m = groups.length; j < m; j++) {
1478     for (var group = groups[j], i = 0, n = group.length, node; i < n; i++) {
1479       if (node = group[i]) callback(node, i, j);
1480     }
1481   }
1482   return groups;
1483 }
1484
1485 d3_selectionPrototype.call = function(callback) {
1486   var args = d3_array(arguments);
1487   callback.apply(args[0] = this, args);
1488   return this;
1489 };
1490
1491 d3_selectionPrototype.empty = function() {
1492   return !this.node();
1493 };
1494
1495 d3_selectionPrototype.node = function() {
1496   for (var j = 0, m = this.length; j < m; j++) {
1497     for (var group = this[j], i = 0, n = group.length; i < n; i++) {
1498       var node = group[i];
1499       if (node) return node;
1500     }
1501   }
1502   return null;
1503 };
1504
1505 function d3_selection_enter(selection) {
1506   d3_arraySubclass(selection, d3_selection_enterPrototype);
1507   return selection;
1508 }
1509
1510 var d3_selection_enterPrototype = [];
1511
1512 d3.selection.enter = d3_selection_enter;
1513 d3.selection.enter.prototype = d3_selection_enterPrototype;
1514
1515 d3_selection_enterPrototype.append = d3_selectionPrototype.append;
1516 d3_selection_enterPrototype.insert = d3_selectionPrototype.insert;
1517 d3_selection_enterPrototype.empty = d3_selectionPrototype.empty;
1518 d3_selection_enterPrototype.node = d3_selectionPrototype.node;
1519
1520
1521 d3_selection_enterPrototype.select = function(selector) {
1522   var subgroups = [],
1523       subgroup,
1524       subnode,
1525       upgroup,
1526       group,
1527       node;
1528
1529   for (var j = -1, m = this.length; ++j < m;) {
1530     upgroup = (group = this[j]).update;
1531     subgroups.push(subgroup = []);
1532     subgroup.parentNode = group.parentNode;
1533     for (var i = -1, n = group.length; ++i < n;) {
1534       if (node = group[i]) {
1535         subgroup.push(upgroup[i] = subnode = selector.call(group.parentNode, node.__data__, i));
1536         subnode.__data__ = node.__data__;
1537       } else {
1538         subgroup.push(null);
1539       }
1540     }
1541   }
1542
1543   return d3_selection(subgroups);
1544 };
1545
1546 d3_selectionPrototype.transition = function() {
1547   var id = d3_transitionInheritId || ++d3_transitionId,
1548       subgroups = [],
1549       subgroup,
1550       node,
1551       transition = Object.create(d3_transitionInherit);
1552
1553   transition.time = Date.now();
1554
1555   for (var j = -1, m = this.length; ++j < m;) {
1556     subgroups.push(subgroup = []);
1557     for (var group = this[j], i = -1, n = group.length; ++i < n;) {
1558       if (node = group[i]) d3_transitionNode(node, i, id, transition);
1559       subgroup.push(node);
1560     }
1561   }
1562
1563   return d3_transition(subgroups, id);
1564 };
1565
1566 var d3_selectionRoot = d3_selection([[d3_document]]);
1567
1568 d3_selectionRoot[0].parentNode = d3_selectRoot;
1569
1570 // TODO fast singleton implementation!
1571 // TODO select(function)
1572 d3.select = function(selector) {
1573   return typeof selector === "string"
1574       ? d3_selectionRoot.select(selector)
1575       : d3_selection([[selector]]); // assume node
1576 };
1577
1578 // TODO selectAll(function)
1579 d3.selectAll = function(selector) {
1580   return typeof selector === "string"
1581       ? d3_selectionRoot.selectAll(selector)
1582       : d3_selection([d3_array(selector)]); // assume node[]
1583 };
1584
1585 d3.behavior.zoom = function() {
1586   var translate = [0, 0],
1587       translate0, // translate when we started zooming (to avoid drift)
1588       scale = 1,
1589       scale0, // scale when we started touching
1590       scaleExtent = d3_behavior_zoomInfinity,
1591       event = d3_eventDispatch(zoom, "zoom"),
1592       x0,
1593       x1,
1594       y0,
1595       y1,
1596       touchtime; // time of last touchstart (to detect double-tap)
1597
1598   function zoom() {
1599     this.on("mousedown.zoom", mousedown)
1600         .on("mousemove.zoom", mousemove)
1601         .on(d3_behavior_zoomWheel + ".zoom", mousewheel)
1602         .on("dblclick.zoom", dblclick)
1603         .on("touchstart.zoom", touchstart)
1604         .on("touchmove.zoom", touchmove)
1605         .on("touchend.zoom", touchstart);
1606   }
1607
1608   zoom.translate = function(x) {
1609     if (!arguments.length) return translate;
1610     translate = x.map(Number);
1611     rescale();
1612     return zoom;
1613   };
1614
1615   zoom.scale = function(x) {
1616     if (!arguments.length) return scale;
1617     scale = +x;
1618     rescale();
1619     return zoom;
1620   };
1621
1622   zoom.scaleExtent = function(x) {
1623     if (!arguments.length) return scaleExtent;
1624     scaleExtent = x == null ? d3_behavior_zoomInfinity : x.map(Number);
1625     return zoom;
1626   };
1627
1628   zoom.x = function(z) {
1629     if (!arguments.length) return x1;
1630     x1 = z;
1631     x0 = z.copy();
1632     translate = [0, 0];
1633     scale = 1;
1634     return zoom;
1635   };
1636
1637   zoom.y = function(z) {
1638     if (!arguments.length) return y1;
1639     y1 = z;
1640     y0 = z.copy();
1641     translate = [0, 0];
1642     scale = 1;
1643     return zoom;
1644   };
1645
1646   function location(p) {
1647     return [(p[0] - translate[0]) / scale, (p[1] - translate[1]) / scale];
1648   }
1649
1650   function point(l) {
1651     return [l[0] * scale + translate[0], l[1] * scale + translate[1]];
1652   }
1653
1654   function scaleTo(s) {
1655     scale = Math.max(scaleExtent[0], Math.min(scaleExtent[1], s));
1656   }
1657
1658   function translateTo(p, l) {
1659     l = point(l);
1660     translate[0] += p[0] - l[0];
1661     translate[1] += p[1] - l[1];
1662   }
1663
1664   function rescale() {
1665     if (x1) x1.domain(x0.range().map(function(x) { return (x - translate[0]) / scale; }).map(x0.invert));
1666     if (y1) y1.domain(y0.range().map(function(y) { return (y - translate[1]) / scale; }).map(y0.invert));
1667   }
1668
1669   function dispatch(event) {
1670     rescale();
1671     d3.event.preventDefault();
1672     event({type: "zoom", scale: scale, translate: translate});
1673   }
1674
1675   function mousedown() {
1676     var target = this,
1677         event_ = event.of(target, arguments),
1678         eventTarget = d3.event.target,
1679         moved = 0,
1680         w = d3.select(d3_window).on("mousemove.zoom", mousemove).on("mouseup.zoom", mouseup),
1681         l = location(d3.mouse(target));
1682
1683     d3_window.focus();
1684     d3_eventCancel();
1685
1686     function mousemove() {
1687       if (d3.event.which === 0) {
1688         mouseup();
1689         return;
1690       }
1691       moved = 1;
1692       translateTo(d3.mouse(target), l);
1693       dispatch(event_);
1694     }
1695
1696     function mouseup() {
1697       if (moved) d3_eventCancel();
1698       w.on("mousemove.zoom", null).on("mouseup.zoom", null);
1699       if (moved && d3.event.target === eventTarget) d3_eventSuppress(w, "click.zoom");
1700     }
1701   }
1702
1703   function mousewheel() {
1704     if (!translate0) translate0 = location(d3.mouse(this));
1705     scaleTo(Math.pow(2, d3_behavior_zoomDelta() * .002) * scale);
1706     translateTo(d3.mouse(this), translate0);
1707     dispatch(event.of(this, arguments));
1708   }
1709
1710   function mousemove() {
1711     translate0 = null;
1712   }
1713
1714   function dblclick() {
1715     var p = d3.mouse(this), l = location(p), k = Math.log(scale) / Math.LN2;
1716     scaleTo(Math.pow(2, d3.event.shiftKey ? Math.ceil(k) - 1 : Math.floor(k) + 1));
1717     translateTo(p, l);
1718     dispatch(event.of(this, arguments));
1719   }
1720
1721   function touchstart() {
1722     var touches = d3.touches(this),
1723         now = Date.now();
1724
1725     scale0 = scale;
1726     translate0 = {};
1727     touches.forEach(function(t) { translate0[t.identifier] = location(t); });
1728     d3_eventCancel();
1729
1730     if (touches.length === 1) {
1731       if (now - touchtime < 500) { // dbltap
1732         var p = touches[0], l = location(touches[0]);
1733         scaleTo(scale * 2);
1734         translateTo(p, l);
1735         dispatch(event.of(this, arguments));
1736       }
1737       touchtime = now;
1738     }
1739   }
1740
1741   function touchmove() {
1742     var touches = d3.touches(this),
1743         p0 = touches[0],
1744         l0 = translate0[p0.identifier];
1745     if (p1 = touches[1]) {
1746       var p1, l1 = translate0[p1.identifier];
1747       p0 = [(p0[0] + p1[0]) / 2, (p0[1] + p1[1]) / 2];
1748       l0 = [(l0[0] + l1[0]) / 2, (l0[1] + l1[1]) / 2];
1749       scaleTo(d3.event.scale * scale0);
1750     }
1751     translateTo(p0, l0);
1752     touchtime = null;
1753     dispatch(event.of(this, arguments));
1754   }
1755
1756   return d3.rebind(zoom, event, "on");
1757 };
1758
1759 var d3_behavior_zoomInfinity = [0, Infinity]; // default scale extent
1760
1761 // https://developer.mozilla.org/en-US/docs/Mozilla_event_reference/wheel
1762 var d3_behavior_zoomDelta, d3_behavior_zoomWheel
1763     = "onwheel" in d3_document ? (d3_behavior_zoomDelta = function() { return -d3.event.deltaY * (d3.event.deltaMode ? 120 : 1); }, "wheel")
1764     : "onmousewheel" in d3_document ? (d3_behavior_zoomDelta = function() { return d3.event.wheelDelta; }, "mousewheel")
1765     : (d3_behavior_zoomDelta = function() { return -d3.event.detail; }, "MozMousePixelScroll");
1766 function d3_functor(v) {
1767   return typeof v === "function" ? v : function() { return v; };
1768 }
1769
1770 d3.functor = d3_functor;
1771
1772 var d3_timer_id = 0,
1773     d3_timer_byId = {},
1774     d3_timer_queue = null,
1775     d3_timer_interval, // is an interval (or frame) active?
1776     d3_timer_timeout; // is a timeout active?
1777
1778 // The timer will continue to fire until callback returns true.
1779 d3.timer = function(callback, delay, then) {
1780   if (arguments.length < 3) {
1781     if (arguments.length < 2) delay = 0;
1782     else if (!isFinite(delay)) return;
1783     then = Date.now();
1784   }
1785
1786   // If the callback's already in the queue, update it.
1787   var timer = d3_timer_byId[callback.id];
1788   if (timer && timer.callback === callback) {
1789     timer.then = then;
1790     timer.delay = delay;
1791   }
1792
1793   // Otherwise, add the callback to the queue.
1794   else d3_timer_byId[callback.id = ++d3_timer_id] = d3_timer_queue = {
1795     callback: callback,
1796     then: then,
1797     delay: delay,
1798     next: d3_timer_queue
1799   };
1800
1801   // Start animatin'!
1802   if (!d3_timer_interval) {
1803     d3_timer_timeout = clearTimeout(d3_timer_timeout);
1804     d3_timer_interval = 1;
1805     d3_timer_frame(d3_timer_step);
1806   }
1807 };
1808
1809 function d3_timer_step() {
1810   var elapsed,
1811       now = Date.now(),
1812       t1 = d3_timer_queue;
1813
1814   while (t1) {
1815     elapsed = now - t1.then;
1816     if (elapsed >= t1.delay) t1.flush = t1.callback(elapsed);
1817     t1 = t1.next;
1818   }
1819
1820   var delay = d3_timer_flush() - now;
1821   if (delay > 24) {
1822     if (isFinite(delay)) {
1823       clearTimeout(d3_timer_timeout);
1824       d3_timer_timeout = setTimeout(d3_timer_step, delay);
1825     }
1826     d3_timer_interval = 0;
1827   } else {
1828     d3_timer_interval = 1;
1829     d3_timer_frame(d3_timer_step);
1830   }
1831 }
1832
1833 d3.timer.flush = function() {
1834   var elapsed,
1835       now = Date.now(),
1836       t1 = d3_timer_queue;
1837
1838   while (t1) {
1839     elapsed = now - t1.then;
1840     if (!t1.delay) t1.flush = t1.callback(elapsed);
1841     t1 = t1.next;
1842   }
1843
1844   d3_timer_flush();
1845 };
1846
1847 // Flush after callbacks to avoid concurrent queue modification.
1848 function d3_timer_flush() {
1849   var t0 = null,
1850       t1 = d3_timer_queue,
1851       then = Infinity;
1852   while (t1) {
1853     if (t1.flush) {
1854       delete d3_timer_byId[t1.callback.id];
1855       t1 = t0 ? t0.next = t1.next : d3_timer_queue = t1.next;
1856     } else {
1857       then = Math.min(then, t1.then + t1.delay);
1858       t1 = (t0 = t1).next;
1859     }
1860   }
1861   return then;
1862 }
1863
1864 var d3_timer_frame = d3_window.requestAnimationFrame
1865     || d3_window.webkitRequestAnimationFrame
1866     || d3_window.mozRequestAnimationFrame
1867     || d3_window.oRequestAnimationFrame
1868     || d3_window.msRequestAnimationFrame
1869     || function(callback) { setTimeout(callback, 17); };
1870 var π = Math.PI,
1871     ε = 1e-6,
1872     d3_radians = π / 180,
1873     d3_degrees = 180 / π;
1874
1875 function d3_sgn(x) {
1876   return x > 0 ? 1 : x < 0 ? -1 : 0;
1877 }
1878
1879 function d3_acos(x) {
1880   return Math.acos(Math.max(-1, Math.min(1, x)));
1881 }
1882
1883 function d3_asin(x) {
1884   return x > 1 ? π / 2 : x < -1 ? -π / 2 : Math.asin(x);
1885 }
1886
1887 function d3_sinh(x) {
1888   return (Math.exp(x) - Math.exp(-x)) / 2;
1889 }
1890
1891 function d3_cosh(x) {
1892   return (Math.exp(x) + Math.exp(-x)) / 2;
1893 }
1894
1895 function d3_haversin(x) {
1896   return (x = Math.sin(x / 2)) * x;
1897 }
1898 d3.geo = {};
1899 function d3_identity(d) {
1900   return d;
1901 }
1902 function d3_true() {
1903   return true;
1904 }
1905
1906 function d3_geo_spherical(cartesian) {
1907   return [
1908     Math.atan2(cartesian[1], cartesian[0]),
1909     Math.asin(Math.max(-1, Math.min(1, cartesian[2])))
1910   ];
1911 }
1912
1913 function d3_geo_sphericalEqual(a, b) {
1914   return Math.abs(a[0] - b[0]) < ε && Math.abs(a[1] - b[1]) < ε;
1915 }
1916
1917 // General spherical polygon clipping algorithm: takes a polygon, cuts it into
1918 // visible line segments and rejoins the segments by interpolating along the
1919 // clip edge.
1920 function d3_geo_clipPolygon(segments, compare, inside, interpolate, listener) {
1921   var subject = [],
1922       clip = [];
1923
1924   segments.forEach(function(segment) {
1925     if ((n = segment.length - 1) <= 0) return;
1926     var n, p0 = segment[0], p1 = segment[n];
1927
1928     // If the first and last points of a segment are coincident, then treat as
1929     // a closed ring.
1930     // TODO if all rings are closed, then the winding order of the exterior
1931     // ring should be checked.
1932     if (d3_geo_sphericalEqual(p0, p1)) {
1933       listener.lineStart();
1934       for (var i = 0; i < n; ++i) listener.point((p0 = segment[i])[0], p0[1]);
1935       listener.lineEnd();
1936       return;
1937     }
1938
1939     var a = {point: p0, points: segment, other: null, visited: false, entry: true, subject: true},
1940         b = {point: p0, points: [p0], other: a, visited: false, entry: false, subject: false};
1941     a.other = b;
1942     subject.push(a);
1943     clip.push(b);
1944     a = {point: p1, points: [p1], other: null, visited: false, entry: false, subject: true};
1945     b = {point: p1, points: [p1], other: a, visited: false, entry: true, subject: false};
1946     a.other = b;
1947     subject.push(a);
1948     clip.push(b);
1949   });
1950   clip.sort(compare);
1951   d3_geo_clipPolygonLinkCircular(subject);
1952   d3_geo_clipPolygonLinkCircular(clip);
1953   if (!subject.length) return;
1954
1955   if (inside) for (var i = 1, e = !inside(clip[0].point), n = clip.length; i < n; ++i) {
1956     clip[i].entry = (e = !e);
1957   }
1958
1959   var start = subject[0],
1960       current,
1961       points,
1962       point;
1963   while (1) {
1964     // Find first unvisited intersection.
1965     current = start;
1966     while (current.visited) if ((current = current.next) === start) return;
1967     points = current.points;
1968     listener.lineStart();
1969     do {
1970       current.visited = current.other.visited = true;
1971       if (current.entry) {
1972         if (current.subject) {
1973           for (var i = 0; i < points.length; i++) listener.point((point = points[i])[0], point[1]);
1974         } else {
1975           interpolate(current.point, current.next.point, 1, listener);
1976         }
1977         current = current.next;
1978       } else {
1979         if (current.subject) {
1980           points = current.prev.points;
1981           for (var i = points.length; --i >= 0;) listener.point((point = points[i])[0], point[1]);
1982         } else {
1983           interpolate(current.point, current.prev.point, -1, listener);
1984         }
1985         current = current.prev;
1986       }
1987       current = current.other;
1988       points = current.points;
1989     } while (!current.visited);
1990     listener.lineEnd();
1991   }
1992 }
1993
1994 function d3_geo_clipPolygonLinkCircular(array) {
1995   if (!(n = array.length)) return;
1996   var n,
1997       i = 0,
1998       a = array[0],
1999       b;
2000   while (++i < n) {
2001     a.next = b = array[i];
2002     b.prev = a;
2003     a = b;
2004   }
2005   a.next = b = array[0];
2006   b.prev = a;
2007 }
2008
2009 function d3_geo_clip(pointVisible, clipLine, interpolate) {
2010   return function(listener) {
2011     var line = clipLine(listener);
2012
2013     var clip = {
2014       point: point,
2015       lineStart: lineStart,
2016       lineEnd: lineEnd,
2017       polygonStart: function() {
2018         clip.point = pointRing;
2019         clip.lineStart = ringStart;
2020         clip.lineEnd = ringEnd;
2021         invisible = false;
2022         invisibleArea = visibleArea = 0;
2023         segments = [];
2024         listener.polygonStart();
2025       },
2026       polygonEnd: function() {
2027         clip.point = point;
2028         clip.lineStart = lineStart;
2029         clip.lineEnd = lineEnd;
2030
2031         segments = d3.merge(segments);
2032         if (segments.length) {
2033           d3_geo_clipPolygon(segments, d3_geo_clipSort, null, interpolate, listener);
2034         } else if (visibleArea < -ε || invisible && invisibleArea < -ε) {
2035           listener.lineStart();
2036           interpolate(null, null, 1, listener);
2037           listener.lineEnd();
2038         }
2039         listener.polygonEnd();
2040         segments = null;
2041       },
2042       sphere: function() {
2043         listener.polygonStart();
2044         listener.lineStart();
2045         interpolate(null, null, 1, listener);
2046         listener.lineEnd();
2047         listener.polygonEnd();
2048       }
2049     };
2050
2051     function point(λ, φ) { if (pointVisible(λ, φ)) listener.point(λ, φ); }
2052     function pointLine(λ, φ) { line.point(λ, φ); }
2053     function lineStart() { clip.point = pointLine; line.lineStart(); }
2054     function lineEnd() { clip.point = point; line.lineEnd(); }
2055
2056     var segments,
2057         visibleArea,
2058         invisibleArea,
2059         invisible;
2060
2061     var buffer = d3_geo_clipBufferListener(),
2062         ringListener = clipLine(buffer),
2063         ring;
2064
2065     function pointRing(λ, φ) {
2066       ringListener.point(λ, φ);
2067       ring.push([λ, φ]);
2068     }
2069
2070     function ringStart() {
2071       ringListener.lineStart();
2072       ring = [];
2073     }
2074
2075     function ringEnd() {
2076       pointRing(ring[0][0], ring[0][1]);
2077       ringListener.lineEnd();
2078
2079       var clean = ringListener.clean(),
2080           ringSegments = buffer.buffer(),
2081           segment,
2082           n = ringSegments.length;
2083
2084       // TODO compute on-the-fly?
2085       if (!n) {
2086         invisible = true;
2087         invisibleArea += d3_geo_clipAreaRing(ring, -1);
2088         ring = null;
2089         return;
2090       }
2091       ring = null;
2092
2093       // No intersections.
2094       // TODO compute on-the-fly?
2095       if (clean & 1) {
2096         segment = ringSegments[0];
2097         visibleArea += d3_geo_clipAreaRing(segment, 1);
2098         var n = segment.length - 1,
2099             i = -1,
2100             point;
2101         listener.lineStart();
2102         while (++i < n) listener.point((point = segment[i])[0], point[1]);
2103         listener.lineEnd();
2104         return;
2105       }
2106
2107       // Rejoin connected segments.
2108       // TODO reuse bufferListener.rejoin()?
2109       if (n > 1 && clean & 2) ringSegments.push(ringSegments.pop().concat(ringSegments.shift()));
2110
2111       segments.push(ringSegments.filter(d3_geo_clipSegmentLength1));
2112     }
2113
2114     return clip;
2115   };
2116 }
2117
2118 function d3_geo_clipSegmentLength1(segment) {
2119   return segment.length > 1;
2120 }
2121
2122 function d3_geo_clipBufferListener() {
2123   var lines = [],
2124       line;
2125   return {
2126     lineStart: function() { lines.push(line = []); },
2127     point: function(λ, φ) { line.push([λ, φ]); },
2128     lineEnd: d3_noop,
2129     buffer: function() {
2130       var buffer = lines;
2131       lines = [];
2132       line = null;
2133       return buffer;
2134     },
2135     rejoin: function() {
2136       if (lines.length > 1) lines.push(lines.pop().concat(lines.shift()));
2137     }
2138   };
2139 }
2140
2141 // Approximate polygon ring area (×2, since we only need the sign).
2142 // For an invisible polygon ring, we rotate longitudinally by 180°.
2143 // The invisible parameter should be 1, or -1 to rotate longitudinally.
2144 // Based on Robert. G. Chamberlain and William H. Duquette,
2145 // “Some Algorithms for Polygons on a Sphere”,
2146 // http://trs-new.jpl.nasa.gov/dspace/handle/2014/40409
2147 function d3_geo_clipAreaRing(ring, invisible) {
2148   if (!(n = ring.length)) return 0;
2149   var n,
2150       i = 0,
2151       area = 0,
2152       p = ring[0],
2153       λ = p[0],
2154       φ = p[1],
2155       cosφ = Math.cos(φ),
2156       x0 = Math.atan2(invisible * Math.sin(λ) * cosφ, Math.sin(φ)),
2157       y0 = 1 - invisible * Math.cos(λ) * cosφ,
2158       x1 = x0,
2159       x, // λ'; λ rotated to south pole.
2160       y; // φ' = 1 + sin(φ); φ rotated to south pole.
2161   while (++i < n) {
2162     p = ring[i];
2163     cosφ = Math.cos(φ = p[1]);
2164     x = Math.atan2(invisible * Math.sin(λ = p[0]) * cosφ, Math.sin(φ));
2165     y = 1 - invisible * Math.cos(λ) * cosφ;
2166
2167     // If both the current point and the previous point are at the north pole,
2168     // skip this point.
2169     if (Math.abs(y0 - 2) < ε && Math.abs(y - 2) < ε) continue;
2170
2171     // If this or the previous point is at the south pole, or if this segment
2172     // goes through the south pole, the area is 0.
2173     if (Math.abs(y) < ε || Math.abs(y0) < ε) {}
2174
2175     // If this segment goes through either pole…
2176     else if (Math.abs(Math.abs(x - x0) - π) < ε) {
2177       // For the north pole, compute lune area.
2178       if (y + y0 > 2) area += 4 * (x - x0);
2179       // For the south pole, the area is zero.
2180     }
2181
2182     // If the previous point is at the north pole, then compute lune area.
2183     else if (Math.abs(y0 - 2) < ε) area += 4 * (x - x1);
2184
2185     // Otherwise, the spherical triangle area is approximately
2186     // δλ * (1 + sinφ0 + 1 + sinφ) / 2.
2187     else area += ((3 * π + x - x0) % (2 * π) - π) * (y0 + y);
2188
2189     x1 = x0, x0 = x, y0 = y;
2190   }
2191   return area;
2192 }
2193
2194 // Intersection points are sorted along the clip edge. For both antimeridian
2195 // cutting and circle clipping, the same comparison is used.
2196 function d3_geo_clipSort(a, b) {
2197   return ((a = a.point)[0] < 0 ? a[1] - π / 2 - ε : π / 2 - a[1])
2198        - ((b = b.point)[0] < 0 ? b[1] - π / 2 - ε : π / 2 - b[1]);
2199 }
2200
2201 var d3_geo_clipAntimeridian = d3_geo_clip(d3_true, d3_geo_clipAntimeridianLine, d3_geo_clipAntimeridianInterpolate);
2202
2203 // Takes a line and cuts into visible segments. Return values:
2204 //   0: there were intersections or the line was empty.
2205 //   1: no intersections.
2206 //   2: there were intersections, and the first and last segments should be
2207 //      rejoined.
2208 function d3_geo_clipAntimeridianLine(listener) {
2209   var λ0 = NaN,
2210       φ0 = NaN,
2211       sλ0 = NaN,
2212       clean; // no intersections
2213
2214   return {
2215     lineStart: function() {
2216       listener.lineStart();
2217       clean = 1;
2218     },
2219     point: function(λ1, φ1) {
2220       var sλ1 = λ1 > 0 ? π : -π,
2221           dλ = Math.abs(λ1 - λ0);
2222       if (Math.abs(dλ - π) < ε) { // line crosses a pole
2223         listener.point(λ0, φ0 = (φ0 + φ1) / 2 > 0 ? π / 2 : -π / 2);
2224         listener.point(sλ0, φ0);
2225         listener.lineEnd();
2226         listener.lineStart();
2227         listener.point(sλ1, φ0);
2228         listener.point( λ1, φ0);
2229         clean = 0;
2230       } else if (sλ0 !== sλ1 && dλ >= π) { // line crosses antimeridian
2231         // handle degeneracies
2232         if (Math.abs(λ0 - sλ0) < ε) λ0 -= sλ0 * ε;
2233         if (Math.abs(λ1 - sλ1) < ε) λ1 -= sλ1 * ε;
2234         φ0 = d3_geo_clipAntimeridianIntersect(λ0, φ0, λ1, φ1);
2235         listener.point(sλ0, φ0);
2236         listener.lineEnd();
2237         listener.lineStart();
2238         listener.point(sλ1, φ0);
2239         clean = 0;
2240       }
2241       listener.point(λ0 = λ1, φ0 = φ1);
2242       sλ0 = sλ1;
2243     },
2244     lineEnd: function() {
2245       listener.lineEnd();
2246       λ0 = φ0 = NaN;
2247     },
2248     // if there are intersections, we always rejoin the first and last segments.
2249     clean: function() { return 2 - clean; }
2250   };
2251 }
2252
2253 function d3_geo_clipAntimeridianIntersect(λ0, φ0, λ1, φ1) {
2254   var cosφ0,
2255       cosφ1,
2256       sinλ0_λ1 = Math.sin(λ0 - λ1);
2257   return Math.abs(sinλ0_λ1) > ε
2258       ? Math.atan((Math.sin(φ0) * (cosφ1 = Math.cos(φ1)) * Math.sin(λ1)
2259                  - Math.sin(φ1) * (cosφ0 = Math.cos(φ0)) * Math.sin(λ0))
2260                  / (cosφ0 * cosφ1 * sinλ0_λ1))
2261       : (φ0 + φ1) / 2;
2262 }
2263
2264 function d3_geo_clipAntimeridianInterpolate(from, to, direction, listener) {
2265   var φ;
2266   if (from == null) {
2267     φ = direction * π / 2;
2268     listener.point(-π,  φ);
2269     listener.point( 0,  φ);
2270     listener.point( π,  φ);
2271     listener.point( π,  0);
2272     listener.point( π, -φ);
2273     listener.point( 0, -φ);
2274     listener.point(-π, -φ);
2275     listener.point(-π,  0);
2276     listener.point(-π,  φ);
2277   } else if (Math.abs(from[0] - to[0]) > ε) {
2278     var s = (from[0] < to[0] ? 1 : -1) * π;
2279     φ = direction * s / 2;
2280     listener.point(-s, φ);
2281     listener.point( 0, φ);
2282     listener.point( s, φ);
2283   } else {
2284     listener.point(to[0], to[1]);
2285   }
2286 }
2287 // TODO
2288 // cross and scale return new vectors,
2289 // whereas add and normalize operate in-place
2290
2291 function d3_geo_cartesian(spherical) {
2292   var λ = spherical[0],
2293       φ = spherical[1],
2294       cosφ = Math.cos(φ);
2295   return [
2296     cosφ * Math.cos(λ),
2297     cosφ * Math.sin(λ),
2298     Math.sin(φ)
2299   ];
2300 }
2301
2302 function d3_geo_cartesianDot(a, b) {
2303   return a[0] * b[0] + a[1] * b[1] + a[2] * b[2];
2304 }
2305
2306 function d3_geo_cartesianCross(a, b) {
2307   return [
2308     a[1] * b[2] - a[2] * b[1],
2309     a[2] * b[0] - a[0] * b[2],
2310     a[0] * b[1] - a[1] * b[0]
2311   ];
2312 }
2313
2314 function d3_geo_cartesianAdd(a, b) {
2315   a[0] += b[0];
2316   a[1] += b[1];
2317   a[2] += b[2];
2318 }
2319
2320 function d3_geo_cartesianScale(vector, k) {
2321   return [
2322     vector[0] * k,
2323     vector[1] * k,
2324     vector[2] * k
2325   ];
2326 }
2327
2328 function d3_geo_cartesianNormalize(d) {
2329   var l = Math.sqrt(d[0] * d[0] + d[1] * d[1] + d[2] * d[2]);
2330   d[0] /= l;
2331   d[1] /= l;
2332   d[2] /= l;
2333 }
2334
2335 function d3_geo_equirectangular(λ, φ) {
2336   return [λ, φ];
2337 }
2338
2339 (d3.geo.equirectangular = function() {
2340   return d3_geo_projection(d3_geo_equirectangular);
2341 }).raw = d3_geo_equirectangular.invert = d3_geo_equirectangular;
2342
2343 d3.geo.rotation = function(rotate) {
2344   rotate = d3_geo_rotation(rotate[0] % 360 * d3_radians, rotate[1] * d3_radians, rotate.length > 2 ? rotate[2] * d3_radians : 0);
2345
2346   function forward(coordinates) {
2347     coordinates = rotate(coordinates[0] * d3_radians, coordinates[1] * d3_radians);
2348     return coordinates[0] *= d3_degrees, coordinates[1] *= d3_degrees, coordinates;
2349   }
2350
2351   forward.invert = function(coordinates) {
2352     coordinates = rotate.invert(coordinates[0] * d3_radians, coordinates[1] * d3_radians);
2353     return coordinates[0] *= d3_degrees, coordinates[1] *= d3_degrees, coordinates;
2354   };
2355
2356   return forward;
2357 };
2358
2359 // Note: |δλ| must be < 2π
2360 function d3_geo_rotation(δλ, δφ, δγ) {
2361   return δλ ? (δφ || δγ ? d3_geo_compose(d3_geo_rotationλ(δλ), d3_geo_rotationφγ(δφ, δγ))
2362     : d3_geo_rotationλ(δλ))
2363     : (δφ || δγ ? d3_geo_rotationφγ(δφ, δγ)
2364     : d3_geo_equirectangular);
2365 }
2366
2367 function d3_geo_forwardRotationλ(δλ) {
2368   return function(λ, φ) {
2369     return λ += δλ, [λ > π ? λ - 2 * π : λ < -π ? λ + 2 * π : λ, φ];
2370   };
2371 }
2372
2373 function d3_geo_rotationλ(δλ) {
2374   var rotation = d3_geo_forwardRotationλ(δλ);
2375   rotation.invert = d3_geo_forwardRotationλ(-δλ);
2376   return rotation;
2377 }
2378
2379 function d3_geo_rotationφγ(δφ, δγ) {
2380   var cosδφ = Math.cos(δφ),
2381       sinδφ = Math.sin(δφ),
2382       cosδγ = Math.cos(δγ),
2383       sinδγ = Math.sin(δγ);
2384
2385   function rotation(λ, φ) {
2386     var cosφ = Math.cos(φ),
2387         x = Math.cos(λ) * cosφ,
2388         y = Math.sin(λ) * cosφ,
2389         z = Math.sin(φ),
2390         k = z * cosδφ + x * sinδφ;
2391     return [
2392       Math.atan2(y * cosδγ - k * sinδγ, x * cosδφ - z * sinδφ),
2393       Math.asin(Math.max(-1, Math.min(1, k * cosδγ + y * sinδγ)))
2394     ];
2395   }
2396
2397   rotation.invert = function(λ, φ) {
2398     var cosφ = Math.cos(φ),
2399         x = Math.cos(λ) * cosφ,
2400         y = Math.sin(λ) * cosφ,
2401         z = Math.sin(φ),
2402         k = z * cosδγ - y * sinδγ;
2403     return [
2404       Math.atan2(y * cosδγ + z * sinδγ, x * cosδφ + k * sinδφ),
2405       Math.asin(Math.max(-1, Math.min(1, k * cosδφ - x * sinδφ)))
2406     ];
2407   };
2408
2409   return rotation;
2410 }
2411
2412 d3.geo.circle = function() {
2413   var origin = [0, 0],
2414       angle,
2415       precision = 6,
2416       interpolate;
2417
2418   function circle() {
2419     var center = typeof origin === "function" ? origin.apply(this, arguments) : origin,
2420         rotate = d3_geo_rotation(-center[0] * d3_radians, -center[1] * d3_radians, 0).invert,
2421         ring = [];
2422
2423     interpolate(null, null, 1, {
2424       point: function(x, y) {
2425         ring.push(x = rotate(x, y));
2426         x[0] *= d3_degrees, x[1] *= d3_degrees;
2427       }
2428     });
2429
2430     return {type: "Polygon", coordinates: [ring]};
2431   }
2432
2433   circle.origin = function(x) {
2434     if (!arguments.length) return origin;
2435     origin = x;
2436     return circle;
2437   };
2438
2439   circle.angle = function(x) {
2440     if (!arguments.length) return angle;
2441     interpolate = d3_geo_circleInterpolate((angle = +x) * d3_radians, precision * d3_radians);
2442     return circle;
2443   };
2444
2445   circle.precision = function(_) {
2446     if (!arguments.length) return precision;
2447     interpolate = d3_geo_circleInterpolate(angle * d3_radians, (precision = +_) * d3_radians);
2448     return circle;
2449   };
2450
2451   return circle.angle(90);
2452 };
2453
2454 // Interpolates along a circle centered at [0°, 0°], with a given radius and
2455 // precision.
2456 function d3_geo_circleInterpolate(radius, precision) {
2457   var cr = Math.cos(radius),
2458       sr = Math.sin(radius);
2459   return function(from, to, direction, listener) {
2460     if (from != null) {
2461       from = d3_geo_circleAngle(cr, from);
2462       to = d3_geo_circleAngle(cr, to);
2463       if (direction > 0 ? from < to: from > to) from += direction * 2 * π;
2464     } else {
2465       from = radius + direction * 2 * π;
2466       to = radius;
2467     }
2468     var point;
2469     for (var step = direction * precision, t = from; direction > 0 ? t > to : t < to; t -= step) {
2470       listener.point((point = d3_geo_spherical([
2471         cr,
2472         -sr * Math.cos(t),
2473         -sr * Math.sin(t)
2474       ]))[0], point[1]);
2475     }
2476   };
2477 }
2478
2479 // Signed angle of a cartesian point relative to [cr, 0, 0].
2480 function d3_geo_circleAngle(cr, point) {
2481   var a = d3_geo_cartesian(point);
2482   a[0] -= cr;
2483   d3_geo_cartesianNormalize(a);
2484   var angle = d3_acos(-a[1]);
2485   return ((-a[2] < 0 ? -angle : angle) + 2 * Math.PI - ε) % (2 * Math.PI);
2486 }
2487
2488 // Clip features against a small circle centered at [0°, 0°].
2489 function d3_geo_clipCircle(radius) {
2490   var cr = Math.cos(radius),
2491       smallRadius = cr > 0,
2492       notHemisphere = Math.abs(cr) > ε, // TODO optimise for this common case
2493       interpolate = d3_geo_circleInterpolate(radius, 6 * d3_radians);
2494
2495   return d3_geo_clip(visible, clipLine, interpolate);
2496
2497   function visible(λ, φ) {
2498     return Math.cos(λ) * Math.cos(φ) > cr;
2499   }
2500
2501   // Takes a line and cuts into visible segments. Return values used for
2502   // polygon clipping:
2503   //   0: there were intersections or the line was empty.
2504   //   1: no intersections.
2505   //   2: there were intersections, and the first and last segments should be
2506   //      rejoined.
2507   function clipLine(listener) {
2508     var point0, // previous point
2509         c0, // code for previous point
2510         v0, // visibility of previous point
2511         v00, // visibility of first point
2512         clean; // no intersections
2513     return {
2514       lineStart: function() {
2515         v00 = v0 = false;
2516         clean = 1;
2517       },
2518       point: function(λ, φ) {
2519         var point1 = [λ, φ],
2520             point2,
2521             v = visible(λ, φ),
2522             c = smallRadius
2523               ? v ? 0 : code(λ, φ)
2524               : v ? code(λ + (λ < 0 ? π : -π), φ) : 0;
2525         if (!point0 && (v00 = v0 = v)) listener.lineStart();
2526         // Handle degeneracies.
2527         // TODO ignore if not clipping polygons.
2528         if (v !== v0) {
2529           point2 = intersect(point0, point1);
2530           if (d3_geo_sphericalEqual(point0, point2) || d3_geo_sphericalEqual(point1, point2)) {
2531             point1[0] += ε;
2532             point1[1] += ε;
2533             v = visible(point1[0], point1[1]);
2534           }
2535         }
2536         if (v !== v0) {
2537           clean = 0;
2538           if (v) {
2539             // outside going in
2540             listener.lineStart();
2541             point2 = intersect(point1, point0);
2542             listener.point(point2[0], point2[1]);
2543           } else {
2544             // inside going out
2545             point2 = intersect(point0, point1);
2546             listener.point(point2[0], point2[1]);
2547             listener.lineEnd();
2548           }
2549           point0 = point2;
2550         } else if (notHemisphere && point0 && smallRadius ^ v) {
2551           var t;
2552           // If the codes for two points are different, or are both zero,
2553           // and there this segment intersects with the small circle.
2554           if (!(c & c0) && (t = intersect(point1, point0, true))) {
2555             clean = 0;
2556             if (smallRadius) {
2557               listener.lineStart();
2558               listener.point(t[0][0], t[0][1]);
2559               listener.point(t[1][0], t[1][1]);
2560               listener.lineEnd();
2561             } else {
2562               listener.point(t[1][0], t[1][1]);
2563               listener.lineEnd();
2564               listener.lineStart();
2565               listener.point(t[0][0], t[0][1]);
2566             }
2567           }
2568         }
2569         if (v && (!point0 || !d3_geo_sphericalEqual(point0, point1))) {
2570           listener.point(point1[0], point1[1]);
2571         }
2572         point0 = point1, v0 = v, c0 = c;
2573       },
2574       lineEnd: function() {
2575         if (v0) listener.lineEnd();
2576         point0 = null;
2577       },
2578       // Rejoin first and last segments if there were intersections and the first
2579       // and last points were visible.
2580       clean: function() { return clean | ((v00 && v0) << 1); }
2581     };
2582   }
2583
2584   // Intersects the great circle between a and b with the clip circle.
2585   function intersect(a, b, two) {
2586     var pa = d3_geo_cartesian(a),
2587         pb = d3_geo_cartesian(b);
2588
2589     // We have two planes, n1.p = d1 and n2.p = d2.
2590     // Find intersection line p(t) = c1 n1 + c2 n2 + t (n1 ⨯ n2).
2591     var n1 = [1, 0, 0], // normal
2592         n2 = d3_geo_cartesianCross(pa, pb),
2593         n2n2 = d3_geo_cartesianDot(n2, n2),
2594         n1n2 = n2[0], // d3_geo_cartesianDot(n1, n2),
2595         determinant = n2n2 - n1n2 * n1n2;
2596
2597     // Two polar points.
2598     if (!determinant) return !two && a;
2599
2600     var c1 =  cr * n2n2 / determinant,
2601         c2 = -cr * n1n2 / determinant,
2602         n1xn2 = d3_geo_cartesianCross(n1, n2),
2603         A = d3_geo_cartesianScale(n1, c1),
2604         B = d3_geo_cartesianScale(n2, c2);
2605     d3_geo_cartesianAdd(A, B);
2606
2607     // Solve |p(t)|^2 = 1.
2608     var u = n1xn2,
2609         w = d3_geo_cartesianDot(A, u),
2610         uu = d3_geo_cartesianDot(u, u),
2611         t2 = w * w - uu * (d3_geo_cartesianDot(A, A) - 1);
2612
2613     if (t2 < 0) return;
2614
2615     var t = Math.sqrt(t2),
2616         q = d3_geo_cartesianScale(u, (-w - t) / uu);
2617     d3_geo_cartesianAdd(q, A);
2618     q = d3_geo_spherical(q);
2619     if (!two) return q;
2620
2621     // Two intersection points.
2622     var λ0 = a[0],
2623         λ1 = b[0],
2624         φ0 = a[1],
2625         φ1 = b[1],
2626         z;
2627     if (λ1 < λ0) z = λ0, λ0 = λ1, λ1 = z;
2628     var δλ = λ1 - λ0,
2629         polar = Math.abs(δλ - π) < ε,
2630         meridian = polar || δλ < ε;
2631
2632     if (!polar && φ1 < φ0) z = φ0, φ0 = φ1, φ1 = z;
2633
2634     // Check that the first point is between a and b.
2635     if (meridian
2636         ? polar
2637           ? φ0 + φ1 > 0 ^ q[1] < (Math.abs(q[0] - λ0) < ε ? φ0 : φ1)
2638           : φ0 <= q[1] && q[1] <= φ1
2639         : δλ > π ^ (λ0 <= q[0] && q[0] <= λ1)) {
2640       var q1 = d3_geo_cartesianScale(u, (-w + t) / uu);
2641       d3_geo_cartesianAdd(q1, A);
2642       return [q, d3_geo_spherical(q1)];
2643     }
2644   }
2645
2646   // Generates a 4-bit vector representing the location of a point relative to
2647   // the small circle's bounding box.
2648   function code(λ, φ) {
2649     var r = smallRadius ? radius : π - radius,
2650         code = 0;
2651     if (λ < -r) code |= 1; // left
2652     else if (λ > r) code |= 2; // right
2653     if (φ < -r) code |= 4; // below
2654     else if (φ > r) code |= 8; // above
2655     return code;
2656   }
2657 }
2658
2659 var d3_geo_clipViewMAX = 1e9;
2660
2661 function d3_geo_clipView(x0, y0, x1, y1) {
2662   return function(listener) {
2663     var listener_ = listener,
2664         bufferListener = d3_geo_clipBufferListener(),
2665         segments,
2666         polygon,
2667         ring;
2668
2669     var clip = {
2670       point: point,
2671       lineStart: lineStart,
2672       lineEnd: lineEnd,
2673       polygonStart: function() {
2674         listener = bufferListener;
2675         segments = [];
2676         polygon = [];
2677       },
2678       polygonEnd: function() {
2679         listener = listener_;
2680         if ((segments = d3.merge(segments)).length) {
2681           listener.polygonStart();
2682           d3_geo_clipPolygon(segments, compare, inside, interpolate, listener);
2683           listener.polygonEnd();
2684         } else if (insidePolygon([x0, y0])) {
2685           listener.polygonStart(), listener.lineStart();
2686           interpolate(null, null, 1, listener);
2687           listener.lineEnd(), listener.polygonEnd();
2688         }
2689         segments = polygon = ring = null;
2690       }
2691     };
2692
2693     function inside(point) {
2694       var a = corner(point, -1),
2695           i = insidePolygon([a === 0 || a === 3 ? x0 : x1, a > 1 ? y1 : y0]);
2696       return i;
2697     }
2698
2699     function insidePolygon(p) {
2700       var wn = 0, // the winding number counter
2701           n = polygon.length,
2702           y = p[1];
2703
2704       for (var i = 0; i < n; ++i) {
2705         for (var j = 1, v = polygon[i], m = v.length, a = v[0]; j < m; ++j) {
2706           b = v[j];
2707           if (a[1] <= y) {
2708             if (b[1] >  y && isLeft(a, b, p) > 0) ++wn;
2709           } else {
2710             if (b[1] <= y && isLeft(a, b, p) < 0) --wn;
2711           }
2712           a = b;
2713         }
2714       }
2715       return wn !== 0;
2716     }
2717
2718     function isLeft(a, b, c) {
2719       return (b[0] - a[0]) * (c[1] - a[1]) - (c[0] - a[0]) * (b[1] - a[1]);
2720     }
2721
2722     function interpolate(from, to, direction, listener) {
2723       var a = 0, a1 = 0;
2724       if (from == null ||
2725           (a = corner(from, direction)) !== (a1 = corner(to, direction)) ||
2726           comparePoints(from, to) < 0 ^ direction > 0) {
2727         do {
2728           listener.point(a === 0 || a === 3 ? x0 : x1, a > 1 ? y1 : y0);
2729         } while ((a = (a + direction + 4) % 4) !== a1);
2730       } else {
2731         listener.point(to[0], to[1]);
2732       }
2733     }
2734
2735     function visible(x, y) {
2736       return x0 <= x && x <= x1 && y0 <= y && y <= y1;
2737     }
2738
2739     function point(x, y) {
2740       if (visible(x, y)) listener.point(x, y);
2741     }
2742
2743     var x__, y__, v__, // first point
2744         x_, y_, v_, // previous point
2745         first;
2746
2747     function lineStart() {
2748       clip.point = linePoint;
2749       if (polygon) polygon.push(ring = []);
2750       first = true;
2751       v_ = false;
2752       x_ = y_ = NaN;
2753     }
2754
2755     function lineEnd() {
2756       // TODO rather than special-case polygons, simply handle them separately.
2757       // Ideally, coincident intersection points should be jittered to avoid
2758       // clipping issues.
2759       if (segments) {
2760         linePoint(x__, y__);
2761         if (v__ && v_) bufferListener.rejoin();
2762         segments.push(bufferListener.buffer());
2763       }
2764       clip.point = point;
2765       if (v_) listener.lineEnd();
2766     }
2767
2768     function linePoint(x, y) {
2769       x = Math.max(-d3_geo_clipViewMAX, Math.min(d3_geo_clipViewMAX, x));
2770       y = Math.max(-d3_geo_clipViewMAX, Math.min(d3_geo_clipViewMAX, y));
2771       var v = visible(x, y);
2772       if (polygon) ring.push([x, y]);
2773       if (first) {
2774         x__ = x, y__ = y, v__ = v;
2775         first = false;
2776         if (v) {
2777           listener.lineStart();
2778           listener.point(x, y);
2779         }
2780       } else {
2781         if (v && v_) listener.point(x, y);
2782         else {
2783           var a = [x_, y_],
2784               b = [x, y];
2785           if (clipLine(a, b)) {
2786             if (!v_) {
2787               listener.lineStart();
2788               listener.point(a[0], a[1]);
2789             }
2790             listener.point(b[0], b[1]);
2791             if (!v) listener.lineEnd();
2792           } else {
2793             listener.lineStart();
2794             listener.point(x, y);
2795           }
2796         }
2797       }
2798       x_ = x, y_ = y, v_ = v;
2799     }
2800
2801     return clip;
2802   };
2803
2804   function corner(p, direction) {
2805     return Math.abs(p[0] - x0) < ε ? direction > 0 ? 0 : 3
2806         : Math.abs(p[0] - x1) < ε ? direction > 0 ? 2 : 1
2807         : Math.abs(p[1] - y0) < ε ? direction > 0 ? 1 : 0
2808         : direction > 0 ? 3 : 2; // Math.abs(p[1] - y1) < ε
2809   }
2810
2811   function compare(a, b) {
2812     return comparePoints(a.point, b.point);
2813   }
2814
2815   function comparePoints(a, b) {
2816     var ca = corner(a, 1),
2817         cb = corner(b, 1);
2818     return ca !== cb ? ca - cb
2819         : ca === 0 ? b[1] - a[1]
2820         : ca === 1 ? a[0] - b[0]
2821         : ca === 2 ? a[1] - b[1]
2822         : b[0] - a[0];
2823   }
2824
2825   // Liang–Barsky line clipping.
2826   function clipLine(a, b) {
2827     var dx = b[0] - a[0],
2828         dy = b[1] - a[1],
2829         t = [0, 1];
2830
2831     if (Math.abs(dx) < ε && Math.abs(dy) < ε) return x0 <= a[0] && a[0] <= x1 && y0 <= a[1] && a[1] <= y1;
2832
2833     if (d3_geo_clipViewT(x0 - a[0],  dx, t) &&
2834         d3_geo_clipViewT(a[0] - x1, -dx, t) &&
2835         d3_geo_clipViewT(y0 - a[1],  dy, t) &&
2836         d3_geo_clipViewT(a[1] - y1, -dy, t)) {
2837       if (t[1] < 1) {
2838         b[0] = a[0] + t[1] * dx;
2839         b[1] = a[1] + t[1] * dy;
2840       }
2841       if (t[0] > 0) {
2842         a[0] += t[0] * dx;
2843         a[1] += t[0] * dy;
2844       }
2845       return true;
2846     }
2847
2848     return false;
2849   }
2850 }
2851
2852 function d3_geo_clipViewT(num, denominator, t) {
2853   if (Math.abs(denominator) < ε) return num <= 0;
2854
2855   var u = num / denominator;
2856
2857   if (denominator > 0) {
2858     if (u > t[1]) return false;
2859     if (u > t[0]) t[0] = u;
2860   } else {
2861     if (u < t[0]) return false;
2862     if (u < t[1]) t[1] = u;
2863   }
2864   return true;
2865 }
2866 function d3_geo_compose(a, b) {
2867
2868   function compose(x, y) {
2869     return x = a(x, y), b(x[0], x[1]);
2870   }
2871
2872   if (a.invert && b.invert) compose.invert = function(x, y) {
2873     return x = b.invert(x, y), x && a.invert(x[0], x[1]);
2874   };
2875
2876   return compose;
2877 }
2878
2879 d3.geo.stream = function(object, listener) {
2880   if (object && d3_geo_streamObjectType.hasOwnProperty(object.type)) {
2881     d3_geo_streamObjectType[object.type](object, listener);
2882   } else {
2883     d3_geo_streamGeometry(object, listener);
2884   }
2885 };
2886
2887 function d3_geo_streamGeometry(geometry, listener) {
2888   if (geometry && d3_geo_streamGeometryType.hasOwnProperty(geometry.type)) {
2889     d3_geo_streamGeometryType[geometry.type](geometry, listener);
2890   }
2891 }
2892
2893 var d3_geo_streamObjectType = {
2894   Feature: function(feature, listener) {
2895     d3_geo_streamGeometry(feature.geometry, listener);
2896   },
2897   FeatureCollection: function(object, listener) {
2898     var features = object.features, i = -1, n = features.length;
2899     while (++i < n) d3_geo_streamGeometry(features[i].geometry, listener);
2900   }
2901 };
2902
2903 var d3_geo_streamGeometryType = {
2904   Sphere: function(object, listener) {
2905     listener.sphere();
2906   },
2907   Point: function(object, listener) {
2908     var coordinate = object.coordinates;
2909     listener.point(coordinate[0], coordinate[1]);
2910   },
2911   MultiPoint: function(object, listener) {
2912     var coordinates = object.coordinates, i = -1, n = coordinates.length, coordinate;
2913     while (++i < n) coordinate = coordinates[i], listener.point(coordinate[0], coordinate[1]);
2914   },
2915   LineString: function(object, listener) {
2916     d3_geo_streamLine(object.coordinates, listener, 0);
2917   },
2918   MultiLineString: function(object, listener) {
2919     var coordinates = object.coordinates, i = -1, n = coordinates.length;
2920     while (++i < n) d3_geo_streamLine(coordinates[i], listener, 0);
2921   },
2922   Polygon: function(object, listener) {
2923     d3_geo_streamPolygon(object.coordinates, listener);
2924   },
2925   MultiPolygon: function(object, listener) {
2926     var coordinates = object.coordinates, i = -1, n = coordinates.length;
2927     while (++i < n) d3_geo_streamPolygon(coordinates[i], listener);
2928   },
2929   GeometryCollection: function(object, listener) {
2930     var geometries = object.geometries, i = -1, n = geometries.length;
2931     while (++i < n) d3_geo_streamGeometry(geometries[i], listener);
2932   }
2933 };
2934
2935 function d3_geo_streamLine(coordinates, listener, closed) {
2936   var i = -1, n = coordinates.length - closed, coordinate;
2937   listener.lineStart();
2938   while (++i < n) coordinate = coordinates[i], listener.point(coordinate[0], coordinate[1]);
2939   listener.lineEnd();
2940 }
2941
2942 function d3_geo_streamPolygon(coordinates, listener) {
2943   var i = -1, n = coordinates.length;
2944   listener.polygonStart();
2945   while (++i < n) d3_geo_streamLine(coordinates[i], listener, 1);
2946   listener.polygonEnd();
2947 }
2948
2949 function d3_geo_resample(project) {
2950   var δ2 = .5, // precision, px²
2951       maxDepth = 16;
2952
2953   function resample(stream) {
2954     var λ0, x0, y0, a0, b0, c0; // previous point
2955
2956     var resample = {
2957       point: point,
2958       lineStart: lineStart,
2959       lineEnd: lineEnd,
2960       polygonStart: function() { stream.polygonStart(); resample.lineStart = polygonLineStart; },
2961       polygonEnd: function() { stream.polygonEnd(); resample.lineStart = lineStart; }
2962     };
2963
2964     function point(x, y) {
2965       x = project(x, y);
2966       stream.point(x[0], x[1]);
2967     }
2968
2969     function lineStart() {
2970       x0 = NaN;
2971       resample.point = linePoint;
2972       stream.lineStart();
2973     }
2974
2975     function linePoint(λ, φ) {
2976       var c = d3_geo_cartesian([λ, φ]), p = project(λ, φ);
2977       resampleLineTo(x0, y0, λ0, a0, b0, c0, x0 = p[0], y0 = p[1], λ0 = λ, a0 = c[0], b0 = c[1], c0 = c[2], maxDepth, stream);
2978       stream.point(x0, y0);
2979     }
2980
2981     function lineEnd() {
2982       resample.point = point;
2983       stream.lineEnd();
2984     }
2985
2986     function polygonLineStart() {
2987       var λ00, φ00, x00, y00, a00, b00, c00; // first point
2988
2989       lineStart();
2990
2991       resample.point = function(λ, φ) {
2992         linePoint(λ00 = λ, φ00 = φ), x00 = x0, y00 = y0, a00 = a0, b00 = b0, c00 = c0;
2993         resample.point = linePoint;
2994       };
2995
2996       resample.lineEnd = function() {
2997         resampleLineTo(x0, y0, λ0, a0, b0, c0, x00, y00, λ00, a00, b00, c00, maxDepth, stream);
2998         resample.lineEnd = lineEnd;
2999         lineEnd();
3000       };
3001     }
3002
3003     return resample;
3004   }
3005
3006   function resampleLineTo(x0, y0, λ0, a0, b0, c0, x1, y1, λ1, a1, b1, c1, depth, stream) {
3007     var dx = x1 - x0,
3008         dy = y1 - y0,
3009         d2 = dx * dx + dy * dy;
3010     if (d2 > 4 * δ2 && depth--) {
3011       var a = a0 + a1,
3012           b = b0 + b1,
3013           c = c0 + c1,
3014           m = Math.sqrt(a * a + b * b + c * c),
3015           φ2 = Math.asin(c /= m),
3016           λ2 = Math.abs(Math.abs(c) - 1) < ε ? (λ0 + λ1) / 2 : Math.atan2(b, a),
3017           p = project(λ2, φ2),
3018           x2 = p[0],
3019           y2 = p[1],
3020           dx2 = x2 - x0,
3021           dy2 = y2 - y0,
3022           dz = dy * dx2 - dx * dy2;
3023       if (dz * dz / d2 > δ2 || Math.abs((dx * dx2 + dy * dy2) / d2 - .5) > .3) {
3024         resampleLineTo(x0, y0, λ0, a0, b0, c0, x2, y2, λ2, a /= m, b /= m, c, depth, stream);
3025         stream.point(x2, y2);
3026         resampleLineTo(x2, y2, λ2, a, b, c, x1, y1, λ1, a1, b1, c1, depth, stream);
3027       }
3028     }
3029   }
3030
3031   resample.precision = function(_) {
3032     if (!arguments.length) return Math.sqrt(δ2);
3033     maxDepth = (δ2 = _ * _) > 0 && 16;
3034     return resample;
3035   };
3036
3037   return resample;
3038 }
3039
3040 d3.geo.projection = d3_geo_projection;
3041 d3.geo.projectionMutator = d3_geo_projectionMutator;
3042
3043 function d3_geo_projection(project) {
3044   return d3_geo_projectionMutator(function() { return project; })();
3045 }
3046
3047 function d3_geo_projectionMutator(projectAt) {
3048   var project,
3049       rotate,
3050       projectRotate,
3051       projectResample = d3_geo_resample(function(x, y) { x = project(x, y); return [x[0] * k + δx, δy - x[1] * k]; }),
3052       k = 150, // scale
3053       x = 480, y = 250, // translate
3054       λ = 0, φ = 0, // center
3055       δλ = 0, δφ = 0, δγ = 0, // rotate
3056       δx, δy, // center
3057       preclip = d3_geo_clipAntimeridian,
3058       postclip = d3_identity,
3059       clipAngle = null,
3060       clipExtent = null;
3061
3062   function projection(point) {
3063     point = projectRotate(point[0] * d3_radians, point[1] * d3_radians);
3064     return [point[0] * k + δx, δy - point[1] * k];
3065   }
3066
3067   function invert(point) {
3068     point = projectRotate.invert((point[0] - δx) / k, (δy - point[1]) / k);
3069     return point && [point[0] * d3_degrees, point[1] * d3_degrees];
3070   }
3071
3072   projection.stream = function(stream) {
3073     return d3_geo_projectionRadiansRotate(rotate, preclip(projectResample(postclip(stream))));
3074   };
3075
3076   projection.clipAngle = function(_) {
3077     if (!arguments.length) return clipAngle;
3078     preclip = _ == null ? (clipAngle = _, d3_geo_clipAntimeridian) : d3_geo_clipCircle((clipAngle = +_) * d3_radians);
3079     return projection;
3080   };
3081
3082   projection.clipExtent = function(_) {
3083     if (!arguments.length) return clipExtent;
3084     clipExtent = _;
3085     postclip = _ == null ? d3_identity : d3_geo_clipView(_[0][0], _[0][1], _[1][0], _[1][1]);
3086     return projection;
3087   };
3088
3089   projection.scale = function(_) {
3090     if (!arguments.length) return k;
3091     k = +_;
3092     return reset();
3093   };
3094
3095   projection.translate = function(_) {
3096     if (!arguments.length) return [x, y];
3097     x = +_[0];
3098     y = +_[1];
3099     return reset();
3100   };
3101
3102   projection.center = function(_) {
3103     if (!arguments.length) return [λ * d3_degrees, φ * d3_degrees];
3104     λ = _[0] % 360 * d3_radians;
3105     φ = _[1] % 360 * d3_radians;
3106     return reset();
3107   };
3108
3109   projection.rotate = function(_) {
3110     if (!arguments.length) return [δλ * d3_degrees, δφ * d3_degrees, δγ * d3_degrees];
3111     δλ = _[0] % 360 * d3_radians;
3112     δφ = _[1] % 360 * d3_radians;
3113     δγ = _.length > 2 ? _[2] % 360 * d3_radians : 0;
3114     return reset();
3115   };
3116
3117   d3.rebind(projection, projectResample, "precision");
3118
3119   function reset() {
3120     projectRotate = d3_geo_compose(rotate = d3_geo_rotation(δλ, δφ, δγ), project);
3121     var center = project(λ, φ);
3122     δx = x - center[0] * k;
3123     δy = y + center[1] * k;
3124     return projection;
3125   }
3126
3127   return function() {
3128     project = projectAt.apply(this, arguments);
3129     projection.invert = project.invert && invert;
3130     return reset();
3131   };
3132 }
3133
3134 function d3_geo_projectionRadiansRotate(rotate, stream) {
3135   return {
3136     point: function(x, y) {
3137       y = rotate(x * d3_radians, y * d3_radians), x = y[0];
3138       stream.point(x > π ? x - 2 * π : x < -π ? x + 2 * π : x, y[1]);
3139     },
3140     sphere: function() { stream.sphere(); },
3141     lineStart: function() { stream.lineStart(); },
3142     lineEnd: function() { stream.lineEnd(); },
3143     polygonStart: function() { stream.polygonStart(); },
3144     polygonEnd: function() { stream.polygonEnd(); }
3145   };
3146 }
3147
3148 function d3_geo_mercator(λ, φ) {
3149   return [λ, Math.log(Math.tan(π / 4 + φ / 2))];
3150 }
3151
3152 d3_geo_mercator.invert = function(x, y) {
3153   return [x, 2 * Math.atan(Math.exp(y)) - π / 2];
3154 };
3155
3156 function d3_geo_mercatorProjection(project) {
3157   var m = d3_geo_projection(project),
3158       scale = m.scale,
3159       translate = m.translate,
3160       clipExtent = m.clipExtent,
3161       clipAuto;
3162
3163   m.scale = function() {
3164     var v = scale.apply(m, arguments);
3165     return v === m ? (clipAuto ? m.clipExtent(null) : m) : v;
3166   };
3167
3168   m.translate = function() {
3169     var v = translate.apply(m, arguments);
3170     return v === m ? (clipAuto ? m.clipExtent(null) : m) : v;
3171   };
3172
3173   m.clipExtent = function(_) {
3174     var v = clipExtent.apply(m, arguments);
3175     if (v === m) {
3176       if (clipAuto = _ == null) {
3177         var k = π * scale(), t = translate();
3178         clipExtent([[t[0] - k, t[1] - k], [t[0] + k, t[1] + k]]);
3179       }
3180     } else if (clipAuto) {
3181       v = null;
3182     }
3183     return v;
3184   };
3185
3186   return m.clipExtent(null);
3187 }
3188
3189 (d3.geo.mercator = function() {
3190   return d3_geo_mercatorProjection(d3_geo_mercator);
3191 }).raw = d3_geo_mercator;
3192
3193 function d3_geo_conic(projectAt) {
3194   var φ0 = 0,
3195       φ1 = π / 3,
3196       m = d3_geo_projectionMutator(projectAt),
3197       p = m(φ0, φ1);
3198
3199   p.parallels = function(_) {
3200     if (!arguments.length) return [φ0 / π * 180, φ1 / π * 180];
3201     return m(φ0 = _[0] * π / 180, φ1 = _[1] * π / 180);
3202   };
3203
3204   return p;
3205 }
3206
3207 function d3_geo_conicEqualArea(φ0, φ1) {
3208   var sinφ0 = Math.sin(φ0),
3209       n = (sinφ0 + Math.sin(φ1)) / 2,
3210       C = 1 + sinφ0 * (2 * n - sinφ0),
3211       ρ0 = Math.sqrt(C) / n;
3212
3213   function forward(λ, φ) {
3214     var ρ = Math.sqrt(C - 2 * n * Math.sin(φ)) / n;
3215     return [
3216       ρ * Math.sin(λ *= n),
3217       ρ0 - ρ * Math.cos(λ)
3218     ];
3219   }
3220
3221   forward.invert = function(x, y) {
3222     var ρ0_y = ρ0 - y;
3223     return [
3224       Math.atan2(x, ρ0_y) / n,
3225       Math.asin((C - (x * x + ρ0_y * ρ0_y) * n * n) / (2 * n))
3226     ];
3227   };
3228
3229   return forward;
3230 }
3231
3232 (d3.geo.conicEqualArea = function() {
3233   return d3_geo_conic(d3_geo_conicEqualArea);
3234 }).raw = d3_geo_conicEqualArea;
3235
3236 // A composite projection for the United States, 960×500. The set of standard
3237 // parallels for each region comes from USGS, which is published here:
3238 // http://egsc.usgs.gov/isb/pubs/MapProjections/projections.html#albers
3239 d3.geo.albersUsa = function() {
3240   var lower48 = d3.geo.conicEqualArea()
3241       .rotate([98, 0])
3242       .center([0, 38])
3243       .parallels([29.5, 45.5]);
3244
3245   var alaska = d3.geo.conicEqualArea()
3246       .rotate([160, 0])
3247       .center([0, 60])
3248       .parallels([55, 65]);
3249
3250   var hawaii = d3.geo.conicEqualArea()
3251       .rotate([160, 0])
3252       .center([0, 20])
3253       .parallels([8, 18]);
3254
3255   var puertoRico = d3.geo.conicEqualArea()
3256       .rotate([60, 0])
3257       .center([0, 10])
3258       .parallels([8, 18]);
3259
3260   var alaskaInvert,
3261       hawaiiInvert,
3262       puertoRicoInvert;
3263
3264   function albersUsa(coordinates) {
3265     return projection(coordinates)(coordinates);
3266   }
3267
3268   function projection(point) {
3269     var lon = point[0],
3270         lat = point[1];
3271     return lat > 50 ? alaska
3272         : lon < -140 ? hawaii
3273         : lat < 21 ? puertoRico
3274         : lower48;
3275   }
3276
3277   albersUsa.invert = function(coordinates) {
3278     return alaskaInvert(coordinates) || hawaiiInvert(coordinates) || puertoRicoInvert(coordinates) || lower48.invert(coordinates);
3279   };
3280
3281   albersUsa.scale = function(x) {
3282     if (!arguments.length) return lower48.scale();
3283     lower48.scale(x);
3284     alaska.scale(x * .6);
3285     hawaii.scale(x);
3286     puertoRico.scale(x * 1.5);
3287     return albersUsa.translate(lower48.translate());
3288   };
3289
3290   albersUsa.translate = function(x) {
3291     if (!arguments.length) return lower48.translate();
3292     var dz = lower48.scale(),
3293         dx = x[0],
3294         dy = x[1];
3295     lower48.translate(x);
3296     alaska.translate([dx - .40 * dz, dy + .17 * dz]);
3297     hawaii.translate([dx - .19 * dz, dy + .20 * dz]);
3298     puertoRico.translate([dx + .58 * dz, dy + .43 * dz]);
3299
3300     alaskaInvert = d3_geo_albersUsaInvert(alaska, [[-180, 50], [-130, 72]]);
3301     hawaiiInvert = d3_geo_albersUsaInvert(hawaii, [[-164, 18], [-154, 24]]);
3302     puertoRicoInvert = d3_geo_albersUsaInvert(puertoRico, [[-67.5, 17.5], [-65, 19]]);
3303
3304     return albersUsa;
3305   };
3306
3307   return albersUsa.scale(1000);
3308 };
3309
3310 function d3_geo_albersUsaInvert(projection, extent) {
3311   var a = projection(extent[0]),
3312       b = projection([.5 * (extent[0][0] + extent[1][0]), extent[0][1]]),
3313       c = projection([extent[1][0], extent[0][1]]),
3314       d = projection(extent[1]);
3315
3316   var dya = b[1]- a[1],
3317       dxa = b[0]- a[0],
3318       dyb = c[1]- b[1],
3319       dxb = c[0]- b[0];
3320
3321   var ma = dya / dxa,
3322       mb = dyb / dxb;
3323
3324   // Find center of circle going through points [a, b, c].
3325   var cx = .5 * (ma * mb * (a[1] - c[1]) + mb * (a[0] + b[0]) - ma * (b[0] + c[0])) / (mb - ma),
3326       cy = (.5 * (a[0] + b[0]) - cx) / ma + .5 * (a[1] + b[1]);
3327
3328   // Radial distance² from center.
3329   var dx0 = d[0] - cx,
3330       dy0 = d[1] - cy,
3331       dx1 = a[0] - cx,
3332       dy1 = a[1] - cy,
3333       r0 = dx0 * dx0 + dy0 * dy0,
3334       r1 = dx1 * dx1 + dy1 * dy1;
3335
3336   // Angular extent.
3337   var a0 = Math.atan2(dy0, dx0),
3338       a1 = Math.atan2(dy1, dx1);
3339
3340   return function(coordinates) {
3341     var dx = coordinates[0] - cx,
3342         dy = coordinates[1] - cy,
3343         r = dx * dx + dy * dy,
3344         a = Math.atan2(dy, dx);
3345     if (r0 < r && r < r1 && a0 < a && a < a1) return projection.invert(coordinates);
3346   };
3347 }
3348
3349 d3.geo.area = function(object) {
3350   d3_geo_areaSum = 0;
3351   d3.geo.stream(object, d3_geo_area);
3352   return d3_geo_areaSum;
3353 };
3354
3355 var d3_geo_areaSum,
3356     d3_geo_areaRingU,
3357     d3_geo_areaRingV;
3358
3359 var d3_geo_area = {
3360   sphere: function() { d3_geo_areaSum += 4 * π; },
3361   point: d3_noop,
3362   lineStart: d3_noop,
3363   lineEnd: d3_noop,
3364
3365   // Only count area for polygon rings.
3366   polygonStart: function() {
3367     d3_geo_areaRingU = 1, d3_geo_areaRingV = 0;
3368     d3_geo_area.lineStart = d3_geo_areaRingStart;
3369   },
3370   polygonEnd: function() {
3371     var area = 2 * Math.atan2(d3_geo_areaRingV, d3_geo_areaRingU);
3372     d3_geo_areaSum += area < 0 ? 4 * π + area : area;
3373     d3_geo_area.lineStart = d3_geo_area.lineEnd = d3_geo_area.point = d3_noop;
3374   }
3375 };
3376
3377 function d3_geo_areaRingStart() {
3378   var λ00, φ00, λ0, cosφ0, sinφ0; // start point and two previous points
3379
3380   // For the first point, …
3381   d3_geo_area.point = function(λ, φ) {
3382     d3_geo_area.point = nextPoint;
3383     λ0 = (λ00 = λ) * d3_radians, cosφ0 = Math.cos(φ = (φ00 = φ) * d3_radians / 2 + π / 4), sinφ0 = Math.sin(φ);
3384   };
3385
3386   // For subsequent points, …
3387   function nextPoint(λ, φ) {
3388     λ *= d3_radians;
3389     φ = φ * d3_radians / 2 + π / 4; // half the angular distance from south pole
3390
3391     // Spherical excess E for a spherical triangle with vertices: south pole,
3392     // previous point, current point.  Uses a formula derived from Cagnoli’s
3393     // theorem.  See Todhunter, Spherical Trig. (1871), Sec. 103, Eq. (2).
3394     var dλ = λ - λ0,
3395         cosφ = Math.cos(φ),
3396         sinφ = Math.sin(φ),
3397         k = sinφ0 * sinφ,
3398         u0 = d3_geo_areaRingU,
3399         v0 = d3_geo_areaRingV,
3400         u = cosφ0 * cosφ + k * Math.cos(dλ),
3401         v = k * Math.sin(dλ);
3402     // ∑ arg(z) = arg(∏ z), where z = u + iv.
3403     d3_geo_areaRingU = u0 * u - v0 * v;
3404     d3_geo_areaRingV = v0 * u + u0 * v;
3405
3406     // Advance the previous points.
3407     λ0 = λ, cosφ0 = cosφ, sinφ0 = sinφ;
3408   }
3409
3410   // For the last point, return to the start.
3411   d3_geo_area.lineEnd = function() {
3412     nextPoint(λ00, φ00);
3413   };
3414 }
3415
3416 d3.geo.bounds = d3_geo_bounds(d3_identity);
3417
3418 function d3_geo_bounds(projectStream) {
3419   var x0, y0, x1, y1;
3420
3421   var bound = {
3422     point: boundPoint,
3423     lineStart: d3_noop,
3424     lineEnd: d3_noop,
3425
3426     // While inside a polygon, ignore points in holes.
3427     polygonStart: function() { bound.lineEnd = boundPolygonLineEnd; },
3428     polygonEnd: function() { bound.point = boundPoint; }
3429   };
3430
3431   function boundPoint(x, y) {
3432     if (x < x0) x0 = x;
3433     if (x > x1) x1 = x;
3434     if (y < y0) y0 = y;
3435     if (y > y1) y1 = y;
3436   }
3437
3438   function boundPolygonLineEnd() {
3439     bound.point = bound.lineEnd = d3_noop;
3440   }
3441
3442   return function(feature) {
3443     y1 = x1 = -(x0 = y0 = Infinity);
3444     d3.geo.stream(feature, projectStream(bound));
3445     return [[x0, y0], [x1, y1]];
3446   };
3447 }
3448
3449 d3.geo.centroid = function(object) {
3450   d3_geo_centroidDimension = d3_geo_centroidW = d3_geo_centroidX = d3_geo_centroidY = d3_geo_centroidZ = 0;
3451   d3.geo.stream(object, d3_geo_centroid);
3452   var m;
3453   if (d3_geo_centroidW &&
3454       Math.abs(m = Math.sqrt(d3_geo_centroidX * d3_geo_centroidX + d3_geo_centroidY * d3_geo_centroidY + d3_geo_centroidZ * d3_geo_centroidZ)) > ε) {
3455     return [
3456       Math.atan2(d3_geo_centroidY, d3_geo_centroidX) * d3_degrees,
3457       Math.asin(Math.max(-1, Math.min(1, d3_geo_centroidZ / m))) * d3_degrees
3458     ];
3459   }
3460 };
3461
3462 var d3_geo_centroidDimension,
3463     d3_geo_centroidW,
3464     d3_geo_centroidX,
3465     d3_geo_centroidY,
3466     d3_geo_centroidZ;
3467
3468 var d3_geo_centroid = {
3469   sphere: function() {
3470     if (d3_geo_centroidDimension < 2) {
3471       d3_geo_centroidDimension = 2;
3472       d3_geo_centroidW = d3_geo_centroidX = d3_geo_centroidY = d3_geo_centroidZ = 0;
3473     }
3474   },
3475   point: d3_geo_centroidPoint,
3476   lineStart: d3_geo_centroidLineStart,
3477   lineEnd: d3_geo_centroidLineEnd,
3478   polygonStart: function() {
3479     if (d3_geo_centroidDimension < 2) {
3480       d3_geo_centroidDimension = 2;
3481       d3_geo_centroidW = d3_geo_centroidX = d3_geo_centroidY = d3_geo_centroidZ = 0;
3482     }
3483     d3_geo_centroid.lineStart = d3_geo_centroidRingStart;
3484   },
3485   polygonEnd: function() {
3486     d3_geo_centroid.lineStart = d3_geo_centroidLineStart;
3487   }
3488 };
3489
3490 // Arithmetic mean of Cartesian vectors.
3491 function d3_geo_centroidPoint(λ, φ) {
3492   if (d3_geo_centroidDimension) return;
3493   ++d3_geo_centroidW;
3494   λ *= d3_radians;
3495   var cosφ = Math.cos(φ *= d3_radians);
3496   d3_geo_centroidX += (cosφ * Math.cos(λ) - d3_geo_centroidX) / d3_geo_centroidW;
3497   d3_geo_centroidY += (cosφ * Math.sin(λ) - d3_geo_centroidY) / d3_geo_centroidW;
3498   d3_geo_centroidZ += (Math.sin(φ) - d3_geo_centroidZ) / d3_geo_centroidW;
3499 }
3500
3501 function d3_geo_centroidRingStart() {
3502   var λ00, φ00; // first point
3503
3504   d3_geo_centroidDimension = 1;
3505   d3_geo_centroidLineStart();
3506   d3_geo_centroidDimension = 2;
3507
3508   var linePoint = d3_geo_centroid.point;
3509   d3_geo_centroid.point = function(λ, φ) {
3510     linePoint(λ00 = λ, φ00 = φ);
3511   };
3512   d3_geo_centroid.lineEnd = function() {
3513     d3_geo_centroid.point(λ00, φ00);
3514     d3_geo_centroidLineEnd();
3515     d3_geo_centroid.lineEnd = d3_geo_centroidLineEnd;
3516   };
3517 }
3518
3519 function d3_geo_centroidLineStart() {
3520   var x0, y0, z0; // previous point
3521
3522   if (d3_geo_centroidDimension > 1) return;
3523   if (d3_geo_centroidDimension < 1) {
3524     d3_geo_centroidDimension = 1;
3525     d3_geo_centroidW = d3_geo_centroidX = d3_geo_centroidY = d3_geo_centroidZ = 0;
3526   }
3527
3528   d3_geo_centroid.point = function(λ, φ) {
3529     λ *= d3_radians;
3530     var cosφ = Math.cos(φ *= d3_radians);
3531     x0 = cosφ * Math.cos(λ);
3532     y0 = cosφ * Math.sin(λ);
3533     z0 = Math.sin(φ);
3534     d3_geo_centroid.point = nextPoint;
3535   };
3536
3537   function nextPoint(λ, φ) {
3538     λ *= d3_radians;
3539     var cosφ = Math.cos(φ *= d3_radians),
3540         x = cosφ * Math.cos(λ),
3541         y = cosφ * Math.sin(λ),
3542         z = Math.sin(φ),
3543         w = Math.atan2(
3544           Math.sqrt((w = y0 * z - z0 * y) * w + (w = z0 * x - x0 * z) * w + (w = x0 * y - y0 * x) * w),
3545           x0 * x + y0 * y + z0 * z);
3546     d3_geo_centroidW += w;
3547     d3_geo_centroidX += w * (x0 + (x0 = x));
3548     d3_geo_centroidY += w * (y0 + (y0 = y));
3549     d3_geo_centroidZ += w * (z0 + (z0 = z));
3550   }
3551 }
3552
3553 function d3_geo_centroidLineEnd() {
3554   d3_geo_centroid.point = d3_geo_centroidPoint;
3555 }
3556
3557 // TODO Unify this code with d3.geom.polygon area?
3558
3559 var d3_geo_pathAreaSum, d3_geo_pathAreaPolygon, d3_geo_pathArea = {
3560   point: d3_noop,
3561   lineStart: d3_noop,
3562   lineEnd: d3_noop,
3563
3564   // Only count area for polygon rings.
3565   polygonStart: function() {
3566     d3_geo_pathAreaPolygon = 0;
3567     d3_geo_pathArea.lineStart = d3_geo_pathAreaRingStart;
3568   },
3569   polygonEnd: function() {
3570     d3_geo_pathArea.lineStart = d3_geo_pathArea.lineEnd = d3_geo_pathArea.point = d3_noop;
3571     d3_geo_pathAreaSum += Math.abs(d3_geo_pathAreaPolygon / 2);
3572   }
3573 };
3574
3575 function d3_geo_pathAreaRingStart() {
3576   var x00, y00, x0, y0;
3577
3578   // For the first point, …
3579   d3_geo_pathArea.point = function(x, y) {
3580     d3_geo_pathArea.point = nextPoint;
3581     x00 = x0 = x, y00 = y0 = y;
3582   };
3583
3584   // For subsequent points, …
3585   function nextPoint(x, y) {
3586     d3_geo_pathAreaPolygon += y0 * x - x0 * y;
3587     x0 = x, y0 = y;
3588   }
3589
3590   // For the last point, return to the start.
3591   d3_geo_pathArea.lineEnd = function() {
3592     nextPoint(x00, y00);
3593   };
3594 }
3595 function d3_geo_pathBuffer() {
3596   var pointCircle = d3_geo_pathCircle(4.5),
3597       buffer = [];
3598
3599   var stream = {
3600     point: point,
3601
3602     // While inside a line, override point to moveTo then lineTo.
3603     lineStart: function() { stream.point = pointLineStart; },
3604     lineEnd: lineEnd,
3605
3606     // While inside a polygon, override lineEnd to closePath.
3607     polygonStart: function() { stream.lineEnd = lineEndPolygon; },
3608     polygonEnd: function() { stream.lineEnd = lineEnd; stream.point = point; },
3609
3610     pointRadius: function(_) {
3611       pointCircle = d3_geo_pathCircle(_);
3612       return stream;
3613     },
3614
3615     result: function() {
3616       if (buffer.length) {
3617         var result = buffer.join("");
3618         buffer = [];
3619         return result;
3620       }
3621     }
3622   };
3623
3624   function point(x, y) {
3625     buffer.push("M", x, ",", y, pointCircle);
3626   }
3627
3628   function pointLineStart(x, y) {
3629     buffer.push("M", x, ",", y);
3630     stream.point = pointLine;
3631   }
3632
3633   function pointLine(x, y) {
3634     buffer.push("L", x, ",", y);
3635   }
3636
3637   function lineEnd() {
3638     stream.point = point;
3639   }
3640
3641   function lineEndPolygon() {
3642     buffer.push("Z");
3643   }
3644
3645   return stream;
3646 }
3647
3648 // TODO Unify this code with d3.geom.polygon centroid?
3649 // TODO Enforce positive area for exterior, negative area for interior?
3650
3651 var d3_geo_pathCentroid = {
3652   point: d3_geo_pathCentroidPoint,
3653
3654   // For lines, weight by length.
3655   lineStart: d3_geo_pathCentroidLineStart,
3656   lineEnd: d3_geo_pathCentroidLineEnd,
3657
3658   // For polygons, weight by area.
3659   polygonStart: function() {
3660     d3_geo_pathCentroid.lineStart = d3_geo_pathCentroidRingStart;
3661   },
3662   polygonEnd: function() {
3663     d3_geo_pathCentroid.point = d3_geo_pathCentroidPoint;
3664     d3_geo_pathCentroid.lineStart = d3_geo_pathCentroidLineStart;
3665     d3_geo_pathCentroid.lineEnd = d3_geo_pathCentroidLineEnd;
3666   }
3667 };
3668
3669 function d3_geo_pathCentroidPoint(x, y) {
3670   if (d3_geo_centroidDimension) return;
3671   d3_geo_centroidX += x;
3672   d3_geo_centroidY += y;
3673   ++d3_geo_centroidZ;
3674 }
3675
3676 function d3_geo_pathCentroidLineStart() {
3677   var x0, y0;
3678
3679   if (d3_geo_centroidDimension !== 1) {
3680     if (d3_geo_centroidDimension < 1) {
3681       d3_geo_centroidDimension = 1;
3682       d3_geo_centroidX = d3_geo_centroidY = d3_geo_centroidZ = 0;
3683     } else return;
3684   }
3685
3686   d3_geo_pathCentroid.point = function(x, y) {
3687     d3_geo_pathCentroid.point = nextPoint;
3688     x0 = x, y0 = y;
3689   };
3690
3691   function nextPoint(x, y) {
3692     var dx = x - x0, dy = y - y0, z = Math.sqrt(dx * dx + dy * dy);
3693     d3_geo_centroidX += z * (x0 + x) / 2;
3694     d3_geo_centroidY += z * (y0 + y) / 2;
3695     d3_geo_centroidZ += z;
3696     x0 = x, y0 = y;
3697   }
3698 }
3699
3700 function d3_geo_pathCentroidLineEnd() {
3701   d3_geo_pathCentroid.point = d3_geo_pathCentroidPoint;
3702 }
3703
3704 function d3_geo_pathCentroidRingStart() {
3705   var x00, y00, x0, y0;
3706
3707   if (d3_geo_centroidDimension < 2) {
3708     d3_geo_centroidDimension = 2;
3709     d3_geo_centroidX = d3_geo_centroidY = d3_geo_centroidZ = 0;
3710   }
3711
3712   // For the first point, …
3713   d3_geo_pathCentroid.point = function(x, y) {
3714     d3_geo_pathCentroid.point = nextPoint;
3715     x00 = x0 = x, y00 = y0 = y;
3716   };
3717
3718   // For subsequent points, …
3719   function nextPoint(x, y) {
3720     var z = y0 * x - x0 * y;
3721     d3_geo_centroidX += z * (x0 + x);
3722     d3_geo_centroidY += z * (y0 + y);
3723     d3_geo_centroidZ += z * 3;
3724     x0 = x, y0 = y;
3725   }
3726
3727   // For the last point, return to the start.
3728   d3_geo_pathCentroid.lineEnd = function() {
3729     nextPoint(x00, y00);
3730   };
3731 }
3732
3733 function d3_geo_pathContext(context) {
3734   var pointRadius = 4.5;
3735
3736   var stream = {
3737     point: point,
3738
3739     // While inside a line, override point to moveTo then lineTo.
3740     lineStart: function() { stream.point = pointLineStart; },
3741     lineEnd: lineEnd,
3742
3743     // While inside a polygon, override lineEnd to closePath.
3744     polygonStart: function() { stream.lineEnd = lineEndPolygon; },
3745     polygonEnd: function() { stream.lineEnd = lineEnd; stream.point = point; },
3746
3747     pointRadius: function(_) {
3748       pointRadius = _;
3749       return stream;
3750     },
3751
3752     result: d3_noop
3753   };
3754
3755   function point(x, y) {
3756     context.moveTo(x, y);
3757     context.arc(x, y, pointRadius, 0, 2 * π);
3758   }
3759
3760   function pointLineStart(x, y) {
3761     context.moveTo(x, y);
3762     stream.point = pointLine;
3763   }
3764
3765   function pointLine(x, y) {
3766     context.lineTo(x, y);
3767   }
3768
3769   function lineEnd() {
3770     stream.point = point;
3771   }
3772
3773   function lineEndPolygon() {
3774     context.closePath();
3775   }
3776
3777   return stream;
3778 }
3779
3780 d3.geo.path = function() {
3781   var pointRadius = 4.5,
3782       projection,
3783       context,
3784       projectStream,
3785       contextStream;
3786
3787   function path(object) {
3788     if (object) d3.geo.stream(object, projectStream(
3789         contextStream.pointRadius(typeof pointRadius === "function"
3790             ? +pointRadius.apply(this, arguments)
3791             : pointRadius)));
3792     return contextStream.result();
3793   }
3794
3795   path.area = function(object) {
3796     d3_geo_pathAreaSum = 0;
3797     d3.geo.stream(object, projectStream(d3_geo_pathArea));
3798     return d3_geo_pathAreaSum;
3799   };
3800
3801   path.centroid = function(object) {
3802     d3_geo_centroidDimension = d3_geo_centroidX = d3_geo_centroidY = d3_geo_centroidZ = 0;
3803     d3.geo.stream(object, projectStream(d3_geo_pathCentroid));
3804     return d3_geo_centroidZ ? [d3_geo_centroidX / d3_geo_centroidZ, d3_geo_centroidY / d3_geo_centroidZ] : undefined;
3805   };
3806
3807   path.bounds = function(object) {
3808     return d3_geo_bounds(projectStream)(object);
3809   };
3810
3811   path.projection = function(_) {
3812     if (!arguments.length) return projection;
3813     projectStream = (projection = _) ? _.stream || d3_geo_pathProjectStream(_) : d3_identity;
3814     return path;
3815   };
3816
3817   path.context = function(_) {
3818     if (!arguments.length) return context;
3819     contextStream = (context = _) == null ? new d3_geo_pathBuffer : new d3_geo_pathContext(_);
3820     return path;
3821   };
3822
3823   path.pointRadius = function(_) {
3824     if (!arguments.length) return pointRadius;
3825     pointRadius = typeof _ === "function" ? _ : +_;
3826     return path;
3827   };
3828
3829   return path.projection(d3.geo.albersUsa()).context(null);
3830 };
3831
3832 function d3_geo_pathCircle(radius) {
3833   return "m0," + radius
3834       + "a" + radius + "," + radius + " 0 1,1 0," + (-2 * radius)
3835       + "a" + radius + "," + radius + " 0 1,1 0," + (+2 * radius)
3836       + "z";
3837 }
3838
3839 function d3_geo_pathProjectStream(project) {
3840   var resample = d3_geo_resample(function(λ, φ) { return project([λ * d3_degrees, φ * d3_degrees]); });
3841   return function(stream) {
3842     stream = resample(stream);
3843     return {
3844       point: function(λ, φ) { stream.point(λ * d3_radians, φ * d3_radians); },
3845       sphere: function() { stream.sphere(); },
3846       lineStart: function() { stream.lineStart(); },
3847       lineEnd: function() { stream.lineEnd(); },
3848       polygonStart: function() { stream.polygonStart(); },
3849       polygonEnd: function() { stream.polygonEnd(); }
3850     };
3851   };
3852 }
3853 d3.geom = {};
3854
3855 d3.geom.polygon = function(coordinates) {
3856
3857   coordinates.area = function() {
3858     var i = 0,
3859         n = coordinates.length,
3860         area = coordinates[n - 1][1] * coordinates[0][0] - coordinates[n - 1][0] * coordinates[0][1];
3861     while (++i < n) {
3862       area += coordinates[i - 1][1] * coordinates[i][0] - coordinates[i - 1][0] * coordinates[i][1];
3863     }
3864     return area * .5;
3865   };
3866
3867   coordinates.centroid = function(k) {
3868     var i = -1,
3869         n = coordinates.length,
3870         x = 0,
3871         y = 0,
3872         a,
3873         b = coordinates[n - 1],
3874         c;
3875     if (!arguments.length) k = -1 / (6 * coordinates.area());
3876     while (++i < n) {
3877       a = b;
3878       b = coordinates[i];
3879       c = a[0] * b[1] - b[0] * a[1];
3880       x += (a[0] + b[0]) * c;
3881       y += (a[1] + b[1]) * c;
3882     }
3883     return [x * k, y * k];
3884   };
3885
3886   // The Sutherland-Hodgman clipping algorithm.
3887   // Note: requires the clip polygon to be counterclockwise and convex.
3888   coordinates.clip = function(subject) {
3889     var input,
3890         i = -1,
3891         n = coordinates.length,
3892         j,
3893         m,
3894         a = coordinates[n - 1],
3895         b,
3896         c,
3897         d;
3898     while (++i < n) {
3899       input = subject.slice();
3900       subject.length = 0;
3901       b = coordinates[i];
3902       c = input[(m = input.length) - 1];
3903       j = -1;
3904       while (++j < m) {
3905         d = input[j];
3906         if (d3_geom_polygonInside(d, a, b)) {
3907           if (!d3_geom_polygonInside(c, a, b)) {
3908             subject.push(d3_geom_polygonIntersect(c, d, a, b));
3909           }
3910           subject.push(d);
3911         } else if (d3_geom_polygonInside(c, a, b)) {
3912           subject.push(d3_geom_polygonIntersect(c, d, a, b));
3913         }
3914         c = d;
3915       }
3916       a = b;
3917     }
3918     return subject;
3919   };
3920
3921   return coordinates;
3922 };
3923
3924 function d3_geom_polygonInside(p, a, b) {
3925   return (b[0] - a[0]) * (p[1] - a[1]) < (b[1] - a[1]) * (p[0] - a[0]);
3926 }
3927
3928 // Intersect two infinite lines cd and ab.
3929 function d3_geom_polygonIntersect(c, d, a, b) {
3930   var x1 = c[0], x3 = a[0], x21 = d[0] - x1, x43 = b[0] - x3,
3931       y1 = c[1], y3 = a[1], y21 = d[1] - y1, y43 = b[1] - y3,
3932       ua = (x43 * (y1 - y3) - y43 * (x1 - x3)) / (y43 * x21 - x43 * y21);
3933   return [x1 + ua * x21, y1 + ua * y21];
3934 }
3935
3936 var d3_ease_default = function() { return d3_identity; };
3937
3938 var d3_ease = d3.map({
3939   linear: d3_ease_default,
3940   poly: d3_ease_poly,
3941   quad: function() { return d3_ease_quad; },
3942   cubic: function() { return d3_ease_cubic; },
3943   sin: function() { return d3_ease_sin; },
3944   exp: function() { return d3_ease_exp; },
3945   circle: function() { return d3_ease_circle; },
3946   elastic: d3_ease_elastic,
3947   back: d3_ease_back,
3948   bounce: function() { return d3_ease_bounce; }
3949 });
3950
3951 var d3_ease_mode = d3.map({
3952   "in": d3_identity,
3953   "out": d3_ease_reverse,
3954   "in-out": d3_ease_reflect,
3955   "out-in": function(f) { return d3_ease_reflect(d3_ease_reverse(f)); }
3956 });
3957
3958 d3.ease = function(name) {
3959   var i = name.indexOf("-"),
3960       t = i >= 0 ? name.substring(0, i) : name,
3961       m = i >= 0 ? name.substring(i + 1) : "in";
3962   t = d3_ease.get(t) || d3_ease_default;
3963   m = d3_ease_mode.get(m) || d3_identity;
3964   return d3_ease_clamp(m(t.apply(null, Array.prototype.slice.call(arguments, 1))));
3965 };
3966
3967 function d3_ease_clamp(f) {
3968   return function(t) {
3969     return t <= 0 ? 0 : t >= 1 ? 1 : f(t);
3970   };
3971 }
3972
3973 function d3_ease_reverse(f) {
3974   return function(t) {
3975     return 1 - f(1 - t);
3976   };
3977 }
3978
3979 function d3_ease_reflect(f) {
3980   return function(t) {
3981     return .5 * (t < .5 ? f(2 * t) : (2 - f(2 - 2 * t)));
3982   };
3983 }
3984
3985 function d3_ease_quad(t) {
3986   return t * t;
3987 }
3988
3989 function d3_ease_cubic(t) {
3990   return t * t * t;
3991 }
3992
3993 // Optimized clamp(reflect(poly(3))).
3994 function d3_ease_cubicInOut(t) {
3995   if (t <= 0) return 0;
3996   if (t >= 1) return 1;
3997   var t2 = t * t, t3 = t2 * t;
3998   return 4 * (t < .5 ? t3 : 3 * (t - t2) + t3 - .75);
3999 }
4000
4001 function d3_ease_poly(e) {
4002   return function(t) {
4003     return Math.pow(t, e);
4004   };
4005 }
4006
4007 function d3_ease_sin(t) {
4008   return 1 - Math.cos(t * π / 2);
4009 }
4010
4011 function d3_ease_exp(t) {
4012   return Math.pow(2, 10 * (t - 1));
4013 }
4014
4015 function d3_ease_circle(t) {
4016   return 1 - Math.sqrt(1 - t * t);
4017 }
4018
4019 function d3_ease_elastic(a, p) {
4020   var s;
4021   if (arguments.length < 2) p = 0.45;
4022   if (arguments.length) s = p / (2 * π) * Math.asin(1 / a);
4023   else a = 1, s = p / 4;
4024   return function(t) {
4025     return 1 + a * Math.pow(2, 10 * -t) * Math.sin((t - s) * 2 * π / p);
4026   };
4027 }
4028
4029 function d3_ease_back(s) {
4030   if (!s) s = 1.70158;
4031   return function(t) {
4032     return t * t * ((s + 1) * t - s);
4033   };
4034 }
4035
4036 function d3_ease_bounce(t) {
4037   return t < 1 / 2.75 ? 7.5625 * t * t
4038       : t < 2 / 2.75 ? 7.5625 * (t -= 1.5 / 2.75) * t + .75
4039       : t < 2.5 / 2.75 ? 7.5625 * (t -= 2.25 / 2.75) * t + .9375
4040       : 7.5625 * (t -= 2.625 / 2.75) * t + .984375;
4041 }
4042
4043 function d3_transition(groups, id) {
4044   d3_arraySubclass(groups, d3_transitionPrototype);
4045
4046   groups.id = id; // Note: read-only!
4047
4048   return groups;
4049 }
4050
4051 var d3_transitionPrototype = [],
4052     d3_transitionId = 0,
4053     d3_transitionInheritId,
4054     d3_transitionInherit = {ease: d3_ease_cubicInOut, delay: 0, duration: 250};
4055
4056 d3_transitionPrototype.call = d3_selectionPrototype.call;
4057 d3_transitionPrototype.empty = d3_selectionPrototype.empty;
4058 d3_transitionPrototype.node = d3_selectionPrototype.node;
4059
4060 d3.transition = function(selection) {
4061   return arguments.length
4062       ? (d3_transitionInheritId ? selection.transition() : selection)
4063       : d3_selectionRoot.transition();
4064 };
4065
4066 d3.transition.prototype = d3_transitionPrototype;
4067
4068
4069 d3_transitionPrototype.select = function(selector) {
4070   var id = this.id,
4071       subgroups = [],
4072       subgroup,
4073       subnode,
4074       node;
4075
4076   if (typeof selector !== "function") selector = d3_selection_selector(selector);
4077
4078   for (var j = -1, m = this.length; ++j < m;) {
4079     subgroups.push(subgroup = []);
4080     for (var group = this[j], i = -1, n = group.length; ++i < n;) {
4081       if ((node = group[i]) && (subnode = selector.call(node, node.__data__, i))) {
4082         if ("__data__" in node) subnode.__data__ = node.__data__;
4083         d3_transitionNode(subnode, i, id, node.__transition__[id]);
4084         subgroup.push(subnode);
4085       } else {
4086         subgroup.push(null);
4087       }
4088     }
4089   }
4090
4091   return d3_transition(subgroups, id);
4092 };
4093
4094 d3_transitionPrototype.selectAll = function(selector) {
4095   var id = this.id,
4096       subgroups = [],
4097       subgroup,
4098       subnodes,
4099       node,
4100       subnode,
4101       transition;
4102
4103   if (typeof selector !== "function") selector = d3_selection_selectorAll(selector);
4104
4105   for (var j = -1, m = this.length; ++j < m;) {
4106     for (var group = this[j], i = -1, n = group.length; ++i < n;) {
4107       if (node = group[i]) {
4108         transition = node.__transition__[id];
4109         subnodes = selector.call(node, node.__data__, i);
4110         subgroups.push(subgroup = []);
4111         for (var k = -1, o = subnodes.length; ++k < o;) {
4112           d3_transitionNode(subnode = subnodes[k], k, id, transition);
4113           subgroup.push(subnode);
4114         }
4115       }
4116     }
4117   }
4118
4119   return d3_transition(subgroups, id);
4120 };
4121
4122 d3_transitionPrototype.filter = function(filter) {
4123   var subgroups = [],
4124       subgroup,
4125       group,
4126       node;
4127
4128   if (typeof filter !== "function") filter = d3_selection_filter(filter);
4129
4130   for (var j = 0, m = this.length; j < m; j++) {
4131     subgroups.push(subgroup = []);
4132     for (var group = this[j], i = 0, n = group.length; i < n; i++) {
4133       if ((node = group[i]) && filter.call(node, node.__data__, i)) {
4134         subgroup.push(node);
4135       }
4136     }
4137   }
4138
4139   return d3_transition(subgroups, this.id, this.time).ease(this.ease());
4140 };
4141 function d3_Color() {}
4142
4143 d3_Color.prototype.toString = function() {
4144   return this.rgb() + "";
4145 };
4146
4147 d3.hsl = function(h, s, l) {
4148   return arguments.length === 1
4149       ? (h instanceof d3_Hsl ? d3_hsl(h.h, h.s, h.l)
4150       : d3_rgb_parse("" + h, d3_rgb_hsl, d3_hsl))
4151       : d3_hsl(+h, +s, +l);
4152 };
4153
4154 function d3_hsl(h, s, l) {
4155   return new d3_Hsl(h, s, l);
4156 }
4157
4158 function d3_Hsl(h, s, l) {
4159   this.h = h;
4160   this.s = s;
4161   this.l = l;
4162 }
4163
4164 var d3_hslPrototype = d3_Hsl.prototype = new d3_Color;
4165
4166 d3_hslPrototype.brighter = function(k) {
4167   k = Math.pow(0.7, arguments.length ? k : 1);
4168   return d3_hsl(this.h, this.s, this.l / k);
4169 };
4170
4171 d3_hslPrototype.darker = function(k) {
4172   k = Math.pow(0.7, arguments.length ? k : 1);
4173   return d3_hsl(this.h, this.s, k * this.l);
4174 };
4175
4176 d3_hslPrototype.rgb = function() {
4177   return d3_hsl_rgb(this.h, this.s, this.l);
4178 };
4179
4180 function d3_hsl_rgb(h, s, l) {
4181   var m1,
4182       m2;
4183
4184   /* Some simple corrections for h, s and l. */
4185   h = h % 360; if (h < 0) h += 360;
4186   s = s < 0 ? 0 : s > 1 ? 1 : s;
4187   l = l < 0 ? 0 : l > 1 ? 1 : l;
4188
4189   /* From FvD 13.37, CSS Color Module Level 3 */
4190   m2 = l <= .5 ? l * (1 + s) : l + s - l * s;
4191   m1 = 2 * l - m2;
4192
4193   function v(h) {
4194     if (h > 360) h -= 360;
4195     else if (h < 0) h += 360;
4196     if (h < 60) return m1 + (m2 - m1) * h / 60;
4197     if (h < 180) return m2;
4198     if (h < 240) return m1 + (m2 - m1) * (240 - h) / 60;
4199     return m1;
4200   }
4201
4202   function vv(h) {
4203     return Math.round(v(h) * 255);
4204   }
4205
4206   return d3_rgb(vv(h + 120), vv(h), vv(h - 120));
4207 }
4208
4209 d3.hcl = function(h, c, l) {
4210   return arguments.length === 1
4211       ? (h instanceof d3_Hcl ? d3_hcl(h.h, h.c, h.l)
4212       : (h instanceof d3_Lab ? d3_lab_hcl(h.l, h.a, h.b)
4213       : d3_lab_hcl((h = d3_rgb_lab((h = d3.rgb(h)).r, h.g, h.b)).l, h.a, h.b)))
4214       : d3_hcl(+h, +c, +l);
4215 };
4216
4217 function d3_hcl(h, c, l) {
4218   return new d3_Hcl(h, c, l);
4219 }
4220
4221 function d3_Hcl(h, c, l) {
4222   this.h = h;
4223   this.c = c;
4224   this.l = l;
4225 }
4226
4227 var d3_hclPrototype = d3_Hcl.prototype = new d3_Color;
4228
4229 d3_hclPrototype.brighter = function(k) {
4230   return d3_hcl(this.h, this.c, Math.min(100, this.l + d3_lab_K * (arguments.length ? k : 1)));
4231 };
4232
4233 d3_hclPrototype.darker = function(k) {
4234   return d3_hcl(this.h, this.c, Math.max(0, this.l - d3_lab_K * (arguments.length ? k : 1)));
4235 };
4236
4237 d3_hclPrototype.rgb = function() {
4238   return d3_hcl_lab(this.h, this.c, this.l).rgb();
4239 };
4240
4241 function d3_hcl_lab(h, c, l) {
4242   return d3_lab(l, Math.cos(h *= d3_radians) * c, Math.sin(h) * c);
4243 }
4244
4245 d3.lab = function(l, a, b) {
4246   return arguments.length === 1
4247       ? (l instanceof d3_Lab ? d3_lab(l.l, l.a, l.b)
4248       : (l instanceof d3_Hcl ? d3_hcl_lab(l.l, l.c, l.h)
4249       : d3_rgb_lab((l = d3.rgb(l)).r, l.g, l.b)))
4250       : d3_lab(+l, +a, +b);
4251 };
4252
4253 function d3_lab(l, a, b) {
4254   return new d3_Lab(l, a, b);
4255 }
4256
4257 function d3_Lab(l, a, b) {
4258   this.l = l;
4259   this.a = a;
4260   this.b = b;
4261 }
4262
4263 // Corresponds roughly to RGB brighter/darker
4264 var d3_lab_K = 18;
4265
4266 // D65 standard referent
4267 var d3_lab_X = 0.950470,
4268     d3_lab_Y = 1,
4269     d3_lab_Z = 1.088830;
4270
4271 var d3_labPrototype = d3_Lab.prototype = new d3_Color;
4272
4273 d3_labPrototype.brighter = function(k) {
4274   return d3_lab(Math.min(100, this.l + d3_lab_K * (arguments.length ? k : 1)), this.a, this.b);
4275 };
4276
4277 d3_labPrototype.darker = function(k) {
4278   return d3_lab(Math.max(0, this.l - d3_lab_K * (arguments.length ? k : 1)), this.a, this.b);
4279 };
4280
4281 d3_labPrototype.rgb = function() {
4282   return d3_lab_rgb(this.l, this.a, this.b);
4283 };
4284
4285 function d3_lab_rgb(l, a, b) {
4286   var y = (l + 16) / 116,
4287       x = y + a / 500,
4288       z = y - b / 200;
4289   x = d3_lab_xyz(x) * d3_lab_X;
4290   y = d3_lab_xyz(y) * d3_lab_Y;
4291   z = d3_lab_xyz(z) * d3_lab_Z;
4292   return d3_rgb(
4293     d3_xyz_rgb( 3.2404542 * x - 1.5371385 * y - 0.4985314 * z),
4294     d3_xyz_rgb(-0.9692660 * x + 1.8760108 * y + 0.0415560 * z),
4295     d3_xyz_rgb( 0.0556434 * x - 0.2040259 * y + 1.0572252 * z)
4296   );
4297 }
4298
4299 function d3_lab_hcl(l, a, b) {
4300   return d3_hcl(Math.atan2(b, a) * d3_degrees, Math.sqrt(a * a + b * b), l);
4301 }
4302
4303 function d3_lab_xyz(x) {
4304   return x > 0.206893034 ? x * x * x : (x - 4 / 29) / 7.787037;
4305 }
4306 function d3_xyz_lab(x) {
4307   return x > 0.008856 ? Math.pow(x, 1 / 3) : 7.787037 * x + 4 / 29;
4308 }
4309
4310 function d3_xyz_rgb(r) {
4311   return Math.round(255 * (r <= 0.00304 ? 12.92 * r : 1.055 * Math.pow(r, 1 / 2.4) - 0.055));
4312 }
4313
4314 d3.rgb = function(r, g, b) {
4315   return arguments.length === 1
4316       ? (r instanceof d3_Rgb ? d3_rgb(r.r, r.g, r.b)
4317       : d3_rgb_parse("" + r, d3_rgb, d3_hsl_rgb))
4318       : d3_rgb(~~r, ~~g, ~~b);
4319 };
4320
4321 function d3_rgb(r, g, b) {
4322   return new d3_Rgb(r, g, b);
4323 }
4324
4325 function d3_Rgb(r, g, b) {
4326   this.r = r;
4327   this.g = g;
4328   this.b = b;
4329 }
4330
4331 var d3_rgbPrototype = d3_Rgb.prototype = new d3_Color;
4332
4333 d3_rgbPrototype.brighter = function(k) {
4334   k = Math.pow(0.7, arguments.length ? k : 1);
4335   var r = this.r,
4336       g = this.g,
4337       b = this.b,
4338       i = 30;
4339   if (!r && !g && !b) return d3_rgb(i, i, i);
4340   if (r && r < i) r = i;
4341   if (g && g < i) g = i;
4342   if (b && b < i) b = i;
4343   return d3_rgb(
4344       Math.min(255, Math.floor(r / k)),
4345       Math.min(255, Math.floor(g / k)),
4346       Math.min(255, Math.floor(b / k)));
4347 };
4348
4349 d3_rgbPrototype.darker = function(k) {
4350   k = Math.pow(0.7, arguments.length ? k : 1);
4351   return d3_rgb(
4352       Math.floor(k * this.r),
4353       Math.floor(k * this.g),
4354       Math.floor(k * this.b));
4355 };
4356
4357 d3_rgbPrototype.hsl = function() {
4358   return d3_rgb_hsl(this.r, this.g, this.b);
4359 };
4360
4361 d3_rgbPrototype.toString = function() {
4362   return "#" + d3_rgb_hex(this.r) + d3_rgb_hex(this.g) + d3_rgb_hex(this.b);
4363 };
4364
4365 function d3_rgb_hex(v) {
4366   return v < 0x10
4367       ? "0" + Math.max(0, v).toString(16)
4368       : Math.min(255, v).toString(16);
4369 }
4370
4371 function d3_rgb_parse(format, rgb, hsl) {
4372   var r = 0, // red channel; int in [0, 255]
4373       g = 0, // green channel; int in [0, 255]
4374       b = 0, // blue channel; int in [0, 255]
4375       m1, // CSS color specification match
4376       m2, // CSS color specification type (e.g., rgb)
4377       name;
4378
4379   /* Handle hsl, rgb. */
4380   m1 = /([a-z]+)\((.*)\)/i.exec(format);
4381   if (m1) {
4382     m2 = m1[2].split(",");
4383     switch (m1[1]) {
4384       case "hsl": {
4385         return hsl(
4386           parseFloat(m2[0]), // degrees
4387           parseFloat(m2[1]) / 100, // percentage
4388           parseFloat(m2[2]) / 100 // percentage
4389         );
4390       }
4391       case "rgb": {
4392         return rgb(
4393           d3_rgb_parseNumber(m2[0]),
4394           d3_rgb_parseNumber(m2[1]),
4395           d3_rgb_parseNumber(m2[2])
4396         );
4397       }
4398     }
4399   }
4400
4401   /* Named colors. */
4402   if (name = d3_rgb_names.get(format)) return rgb(name.r, name.g, name.b);
4403
4404   /* Hexadecimal colors: #rgb and #rrggbb. */
4405   if (format != null && format.charAt(0) === "#") {
4406     if (format.length === 4) {
4407       r = format.charAt(1); r += r;
4408       g = format.charAt(2); g += g;
4409       b = format.charAt(3); b += b;
4410     } else if (format.length === 7) {
4411       r = format.substring(1, 3);
4412       g = format.substring(3, 5);
4413       b = format.substring(5, 7);
4414     }
4415     r = parseInt(r, 16);
4416     g = parseInt(g, 16);
4417     b = parseInt(b, 16);
4418   }
4419
4420   return rgb(r, g, b);
4421 }
4422
4423 function d3_rgb_hsl(r, g, b) {
4424   var min = Math.min(r /= 255, g /= 255, b /= 255),
4425       max = Math.max(r, g, b),
4426       d = max - min,
4427       h,
4428       s,
4429       l = (max + min) / 2;
4430   if (d) {
4431     s = l < .5 ? d / (max + min) : d / (2 - max - min);
4432     if (r == max) h = (g - b) / d + (g < b ? 6 : 0);
4433     else if (g == max) h = (b - r) / d + 2;
4434     else h = (r - g) / d + 4;
4435     h *= 60;
4436   } else {
4437     s = h = 0;
4438   }
4439   return d3_hsl(h, s, l);
4440 }
4441
4442 function d3_rgb_lab(r, g, b) {
4443   r = d3_rgb_xyz(r);
4444   g = d3_rgb_xyz(g);
4445   b = d3_rgb_xyz(b);
4446   var x = d3_xyz_lab((0.4124564 * r + 0.3575761 * g + 0.1804375 * b) / d3_lab_X),
4447       y = d3_xyz_lab((0.2126729 * r + 0.7151522 * g + 0.0721750 * b) / d3_lab_Y),
4448       z = d3_xyz_lab((0.0193339 * r + 0.1191920 * g + 0.9503041 * b) / d3_lab_Z);
4449   return d3_lab(116 * y - 16, 500 * (x - y), 200 * (y - z));
4450 }
4451
4452 function d3_rgb_xyz(r) {
4453   return (r /= 255) <= 0.04045 ? r / 12.92 : Math.pow((r + 0.055) / 1.055, 2.4);
4454 }
4455
4456 function d3_rgb_parseNumber(c) { // either integer or percentage
4457   var f = parseFloat(c);
4458   return c.charAt(c.length - 1) === "%" ? Math.round(f * 2.55) : f;
4459 }
4460
4461 var d3_rgb_names = d3.map({
4462   aliceblue: "#f0f8ff",
4463   antiquewhite: "#faebd7",
4464   aqua: "#00ffff",
4465   aquamarine: "#7fffd4",
4466   azure: "#f0ffff",
4467   beige: "#f5f5dc",
4468   bisque: "#ffe4c4",
4469   black: "#000000",
4470   blanchedalmond: "#ffebcd",
4471   blue: "#0000ff",
4472   blueviolet: "#8a2be2",
4473   brown: "#a52a2a",
4474   burlywood: "#deb887",
4475   cadetblue: "#5f9ea0",
4476   chartreuse: "#7fff00",
4477   chocolate: "#d2691e",
4478   coral: "#ff7f50",
4479   cornflowerblue: "#6495ed",
4480   cornsilk: "#fff8dc",
4481   crimson: "#dc143c",
4482   cyan: "#00ffff",
4483   darkblue: "#00008b",
4484   darkcyan: "#008b8b",
4485   darkgoldenrod: "#b8860b",
4486   darkgray: "#a9a9a9",
4487   darkgreen: "#006400",
4488   darkgrey: "#a9a9a9",
4489   darkkhaki: "#bdb76b",
4490   darkmagenta: "#8b008b",
4491   darkolivegreen: "#556b2f",
4492   darkorange: "#ff8c00",
4493   darkorchid: "#9932cc",
4494   darkred: "#8b0000",
4495   darksalmon: "#e9967a",
4496   darkseagreen: "#8fbc8f",
4497   darkslateblue: "#483d8b",
4498   darkslategray: "#2f4f4f",
4499   darkslategrey: "#2f4f4f",
4500   darkturquoise: "#00ced1",
4501   darkviolet: "#9400d3",
4502   deeppink: "#ff1493",
4503   deepskyblue: "#00bfff",
4504   dimgray: "#696969",
4505   dimgrey: "#696969",
4506   dodgerblue: "#1e90ff",
4507   firebrick: "#b22222",
4508   floralwhite: "#fffaf0",
4509   forestgreen: "#228b22",
4510   fuchsia: "#ff00ff",
4511   gainsboro: "#dcdcdc",
4512   ghostwhite: "#f8f8ff",
4513   gold: "#ffd700",
4514   goldenrod: "#daa520",
4515   gray: "#808080",
4516   green: "#008000",
4517   greenyellow: "#adff2f",
4518   grey: "#808080",
4519   honeydew: "#f0fff0",
4520   hotpink: "#ff69b4",
4521   indianred: "#cd5c5c",
4522   indigo: "#4b0082",
4523   ivory: "#fffff0",
4524   khaki: "#f0e68c",
4525   lavender: "#e6e6fa",
4526   lavenderblush: "#fff0f5",
4527   lawngreen: "#7cfc00",
4528   lemonchiffon: "#fffacd",
4529   lightblue: "#add8e6",
4530   lightcoral: "#f08080",
4531   lightcyan: "#e0ffff",
4532   lightgoldenrodyellow: "#fafad2",
4533   lightgray: "#d3d3d3",
4534   lightgreen: "#90ee90",
4535   lightgrey: "#d3d3d3",
4536   lightpink: "#ffb6c1",
4537   lightsalmon: "#ffa07a",
4538   lightseagreen: "#20b2aa",
4539   lightskyblue: "#87cefa",
4540   lightslategray: "#778899",
4541   lightslategrey: "#778899",
4542   lightsteelblue: "#b0c4de",
4543   lightyellow: "#ffffe0",
4544   lime: "#00ff00",
4545   limegreen: "#32cd32",
4546   linen: "#faf0e6",
4547   magenta: "#ff00ff",
4548   maroon: "#800000",
4549   mediumaquamarine: "#66cdaa",
4550   mediumblue: "#0000cd",
4551   mediumorchid: "#ba55d3",
4552   mediumpurple: "#9370db",
4553   mediumseagreen: "#3cb371",
4554   mediumslateblue: "#7b68ee",
4555   mediumspringgreen: "#00fa9a",
4556   mediumturquoise: "#48d1cc",
4557   mediumvioletred: "#c71585",
4558   midnightblue: "#191970",
4559   mintcream: "#f5fffa",
4560   mistyrose: "#ffe4e1",
4561   moccasin: "#ffe4b5",
4562   navajowhite: "#ffdead",
4563   navy: "#000080",
4564   oldlace: "#fdf5e6",
4565   olive: "#808000",
4566   olivedrab: "#6b8e23",
4567   orange: "#ffa500",
4568   orangered: "#ff4500",
4569   orchid: "#da70d6",
4570   palegoldenrod: "#eee8aa",
4571   palegreen: "#98fb98",
4572   paleturquoise: "#afeeee",
4573   palevioletred: "#db7093",
4574   papayawhip: "#ffefd5",
4575   peachpuff: "#ffdab9",
4576   peru: "#cd853f",
4577   pink: "#ffc0cb",
4578   plum: "#dda0dd",
4579   powderblue: "#b0e0e6",
4580   purple: "#800080",
4581   red: "#ff0000",
4582   rosybrown: "#bc8f8f",
4583   royalblue: "#4169e1",
4584   saddlebrown: "#8b4513",
4585   salmon: "#fa8072",
4586   sandybrown: "#f4a460",
4587   seagreen: "#2e8b57",
4588   seashell: "#fff5ee",
4589   sienna: "#a0522d",
4590   silver: "#c0c0c0",
4591   skyblue: "#87ceeb",
4592   slateblue: "#6a5acd",
4593   slategray: "#708090",
4594   slategrey: "#708090",
4595   snow: "#fffafa",
4596   springgreen: "#00ff7f",
4597   steelblue: "#4682b4",
4598   tan: "#d2b48c",
4599   teal: "#008080",
4600   thistle: "#d8bfd8",
4601   tomato: "#ff6347",
4602   turquoise: "#40e0d0",
4603   violet: "#ee82ee",
4604   wheat: "#f5deb3",
4605   white: "#ffffff",
4606   whitesmoke: "#f5f5f5",
4607   yellow: "#ffff00",
4608   yellowgreen: "#9acd32"
4609 });
4610
4611 d3_rgb_names.forEach(function(key, value) {
4612   d3_rgb_names.set(key, d3_rgb_parse(value, d3_rgb, d3_hsl_rgb));
4613 });
4614
4615 d3.interpolateRgb = d3_interpolateRgb;
4616
4617 function d3_interpolateRgb(a, b) {
4618   a = d3.rgb(a);
4619   b = d3.rgb(b);
4620   var ar = a.r,
4621       ag = a.g,
4622       ab = a.b,
4623       br = b.r - ar,
4624       bg = b.g - ag,
4625       bb = b.b - ab;
4626   return function(t) {
4627     return "#"
4628         + d3_rgb_hex(Math.round(ar + br * t))
4629         + d3_rgb_hex(Math.round(ag + bg * t))
4630         + d3_rgb_hex(Math.round(ab + bb * t));
4631   };
4632 }
4633
4634 d3.transform = function(string) {
4635   var g = d3_document.createElementNS(d3.ns.prefix.svg, "g");
4636   return (d3.transform = function(string) {
4637     g.setAttribute("transform", string);
4638     var t = g.transform.baseVal.consolidate();
4639     return new d3_transform(t ? t.matrix : d3_transformIdentity);
4640   })(string);
4641 };
4642
4643 // Compute x-scale and normalize the first row.
4644 // Compute shear and make second row orthogonal to first.
4645 // Compute y-scale and normalize the second row.
4646 // Finally, compute the rotation.
4647 function d3_transform(m) {
4648   var r0 = [m.a, m.b],
4649       r1 = [m.c, m.d],
4650       kx = d3_transformNormalize(r0),
4651       kz = d3_transformDot(r0, r1),
4652       ky = d3_transformNormalize(d3_transformCombine(r1, r0, -kz)) || 0;
4653   if (r0[0] * r1[1] < r1[0] * r0[1]) {
4654     r0[0] *= -1;
4655     r0[1] *= -1;
4656     kx *= -1;
4657     kz *= -1;
4658   }
4659   this.rotate = (kx ? Math.atan2(r0[1], r0[0]) : Math.atan2(-r1[0], r1[1])) * d3_degrees;
4660   this.translate = [m.e, m.f];
4661   this.scale = [kx, ky];
4662   this.skew = ky ? Math.atan2(kz, ky) * d3_degrees : 0;
4663 };
4664
4665 d3_transform.prototype.toString = function() {
4666   return "translate(" + this.translate
4667       + ")rotate(" + this.rotate
4668       + ")skewX(" + this.skew
4669       + ")scale(" + this.scale
4670       + ")";
4671 };
4672
4673 function d3_transformDot(a, b) {
4674   return a[0] * b[0] + a[1] * b[1];
4675 }
4676
4677 function d3_transformNormalize(a) {
4678   var k = Math.sqrt(d3_transformDot(a, a));
4679   if (k) {
4680     a[0] /= k;
4681     a[1] /= k;
4682   }
4683   return k;
4684 }
4685
4686 function d3_transformCombine(a, b, k) {
4687   a[0] += k * b[0];
4688   a[1] += k * b[1];
4689   return a;
4690 }
4691
4692 var d3_transformIdentity = {a: 1, b: 0, c: 0, d: 1, e: 0, f: 0};
4693 d3.interpolateNumber = d3_interpolateNumber;
4694
4695 function d3_interpolateNumber(a, b) {
4696   b -= a = +a;
4697   return function(t) { return a + b * t; };
4698 }
4699
4700 d3.interpolateTransform = d3_interpolateTransform;
4701
4702 function d3_interpolateTransform(a, b) {
4703   var s = [], // string constants and placeholders
4704       q = [], // number interpolators
4705       n,
4706       A = d3.transform(a),
4707       B = d3.transform(b),
4708       ta = A.translate,
4709       tb = B.translate,
4710       ra = A.rotate,
4711       rb = B.rotate,
4712       wa = A.skew,
4713       wb = B.skew,
4714       ka = A.scale,
4715       kb = B.scale;
4716
4717   if (ta[0] != tb[0] || ta[1] != tb[1]) {
4718     s.push("translate(", null, ",", null, ")");
4719     q.push({i: 1, x: d3_interpolateNumber(ta[0], tb[0])}, {i: 3, x: d3_interpolateNumber(ta[1], tb[1])});
4720   } else if (tb[0] || tb[1]) {
4721     s.push("translate(" + tb + ")");
4722   } else {
4723     s.push("");
4724   }
4725
4726   if (ra != rb) {
4727     if (ra - rb > 180) rb += 360; else if (rb - ra > 180) ra += 360; // shortest path
4728     q.push({i: s.push(s.pop() + "rotate(", null, ")") - 2, x: d3_interpolateNumber(ra, rb)});
4729   } else if (rb) {
4730     s.push(s.pop() + "rotate(" + rb + ")");
4731   }
4732
4733   if (wa != wb) {
4734     q.push({i: s.push(s.pop() + "skewX(", null, ")") - 2, x: d3_interpolateNumber(wa, wb)});
4735   } else if (wb) {
4736     s.push(s.pop() + "skewX(" + wb + ")");
4737   }
4738
4739   if (ka[0] != kb[0] || ka[1] != kb[1]) {
4740     n = s.push(s.pop() + "scale(", null, ",", null, ")");
4741     q.push({i: n - 4, x: d3_interpolateNumber(ka[0], kb[0])}, {i: n - 2, x: d3_interpolateNumber(ka[1], kb[1])});
4742   } else if (kb[0] != 1 || kb[1] != 1) {
4743     s.push(s.pop() + "scale(" + kb + ")");
4744   }
4745
4746   n = q.length;
4747   return function(t) {
4748     var i = -1, o;
4749     while (++i < n) s[(o = q[i]).i] = o.x(t);
4750     return s.join("");
4751   };
4752 }
4753
4754 d3.interpolateObject = d3_interpolateObject;
4755
4756 function d3_interpolateObject(a, b) {
4757   var i = {},
4758       c = {},
4759       k;
4760   for (k in a) {
4761     if (k in b) {
4762       i[k] = d3_interpolateByName(k)(a[k], b[k]);
4763     } else {
4764       c[k] = a[k];
4765     }
4766   }
4767   for (k in b) {
4768     if (!(k in a)) {
4769       c[k] = b[k];
4770     }
4771   }
4772   return function(t) {
4773     for (k in i) c[k] = i[k](t);
4774     return c;
4775   };
4776 }
4777
4778 d3.interpolateArray = d3_interpolateArray;
4779
4780 function d3_interpolateArray(a, b) {
4781   var x = [],
4782       c = [],
4783       na = a.length,
4784       nb = b.length,
4785       n0 = Math.min(a.length, b.length),
4786       i;
4787   for (i = 0; i < n0; ++i) x.push(d3_interpolate(a[i], b[i]));
4788   for (; i < na; ++i) c[i] = a[i];
4789   for (; i < nb; ++i) c[i] = b[i];
4790   return function(t) {
4791     for (i = 0; i < n0; ++i) c[i] = x[i](t);
4792     return c;
4793   };
4794 }
4795
4796 d3.interpolateString = d3_interpolateString;
4797
4798 function d3_interpolateString(a, b) {
4799   var m, // current match
4800       i, // current index
4801       j, // current index (for coalescing)
4802       s0 = 0, // start index of current string prefix
4803       s1 = 0, // end index of current string prefix
4804       s = [], // string constants and placeholders
4805       q = [], // number interpolators
4806       n, // q.length
4807       o;
4808
4809   // Coerce inputs to strings.
4810   a = a + "", b = b + "";
4811
4812   // Reset our regular expression!
4813   d3_interpolate_number.lastIndex = 0;
4814
4815   // Find all numbers in b.
4816   for (i = 0; m = d3_interpolate_number.exec(b); ++i) {
4817     if (m.index) s.push(b.substring(s0, s1 = m.index));
4818     q.push({i: s.length, x: m[0]});
4819     s.push(null);
4820     s0 = d3_interpolate_number.lastIndex;
4821   }
4822   if (s0 < b.length) s.push(b.substring(s0));
4823
4824   // Find all numbers in a.
4825   for (i = 0, n = q.length; (m = d3_interpolate_number.exec(a)) && i < n; ++i) {
4826     o = q[i];
4827     if (o.x == m[0]) { // The numbers match, so coalesce.
4828       if (o.i) {
4829         if (s[o.i + 1] == null) { // This match is followed by another number.
4830           s[o.i - 1] += o.x;
4831           s.splice(o.i, 1);
4832           for (j = i + 1; j < n; ++j) q[j].i--;
4833         } else { // This match is followed by a string, so coalesce twice.
4834           s[o.i - 1] += o.x + s[o.i + 1];
4835           s.splice(o.i, 2);
4836           for (j = i + 1; j < n; ++j) q[j].i -= 2;
4837         }
4838       } else {
4839           if (s[o.i + 1] == null) { // This match is followed by another number.
4840           s[o.i] = o.x;
4841         } else { // This match is followed by a string, so coalesce twice.
4842           s[o.i] = o.x + s[o.i + 1];
4843           s.splice(o.i + 1, 1);
4844           for (j = i + 1; j < n; ++j) q[j].i--;
4845         }
4846       }
4847       q.splice(i, 1);
4848       n--;
4849       i--;
4850     } else {
4851       o.x = d3_interpolateNumber(parseFloat(m[0]), parseFloat(o.x));
4852     }
4853   }
4854
4855   // Remove any numbers in b not found in a.
4856   while (i < n) {
4857     o = q.pop();
4858     if (s[o.i + 1] == null) { // This match is followed by another number.
4859       s[o.i] = o.x;
4860     } else { // This match is followed by a string, so coalesce twice.
4861       s[o.i] = o.x + s[o.i + 1];
4862       s.splice(o.i + 1, 1);
4863     }
4864     n--;
4865   }
4866
4867   // Special optimization for only a single match.
4868   if (s.length === 1) {
4869     return s[0] == null ? q[0].x : function() { return b; };
4870   }
4871
4872   // Otherwise, interpolate each of the nu